Có ~n~ thành phố và ~m~ chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của tuyến đường ngắn nhất từ ​​Syrjälä đến mọi thành phố.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1,2,\ldots, n~ và thành phố ~1~ là Syrjälä.
• Sau đó, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~ và ~c~: một chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và độ dài của nó là ~c~. Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Output

• In ~n~ số nguyên: độ dài tuyến đường ngắn nhất từ ​​Syrjälä đến các thành phố ~1,2,\ldots, n~.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

3 4
1 2 6
1 3 2
3 2 3
1 3 4

Sample output

0 5 2

Có ~n~ thành phố và ~m~ chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của tuyến đường ngắn nhất từ ​​Syrjälä đến mọi thành phố.˙

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1,2,\ldots, n~ và thành phố ~1~ là Syrjälä.
• Sau đó, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~ và ~c~: một chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và độ dài của nó là ~c~. Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Output

• In ~n~ số nguyên: độ dài tuyến đường ngắn nhất từ ​​Syrjälä đến các thành phố ~1,2,\ldots, n~.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

3 4
1 2 6
1 3 2
3 2 3
1 3 4

Sample output

0 5 2

Cho một ma trận lưới ~n * m~, các ô vuông được thể hiện bởi chữ số. Từ một ô vuông có thể đi sang ~4~ ô kề cạnh. Viết chương trình tìm đường đi từ ~(x,y)~ đến ~(u,v)~ có tổng các ô chữ số là nhỏ nhất.

• ~(i, j)~ là ô hàng ~i~ cột ~j~.
• Ký tự ~G~ là ô ~(x, y)~.
• Ký tự ~R~ là ô ~(u, v)~.

Input

• Dòng đầu tiên: Hai số nguyên dương ~n~ và ~m~
• ~n~ dòng tiếp theo: Mô tả ma trận lưới.
• Giới hạn: ~n, m \le 1000~

Output

• Độ dài đường đi.

Sample Input

3 3
323
G9R
018

Sample Output

8

Một ngày, OG Loc đã mời CJ dự một buổi tiệc rap của anh ta. Và hôm nay buổi tiệc sẽ diễn ra, nhưng CJ vì mải mê công việc, mà khi nhìn vào đồng hồ và lịch thì … CJ mới chợt nhớ ra về bữa tiệc của OG Loc. Mà còn khoảng ~2~ tiếng nữa là buổi tiệc rap của OG Loc sẽ diễn ra.

CJ nhìn vào bản đồ trong vùng. Bản đồ đấy gồm ~N~ ngôi nhà, đánh số từ ~1~ tới ~N~ và ~M~ con đường hai chiều nối hai ngôi nhà. Ngôi nhà của CJ có số hiệu là ~s~, ngôi nhà có bữa tiệc của OG Loc có số hiệu là ~t~. Vì không muốn tới trễ nên CJ quyết định tìm đường đi ngắn nhất từ nhà của mình tới buổi tiệc tại ngôi nhà của OG Loc và sẽ di chuyển theo đường đi đó.

Input

• Gồm ~M + 1~ dòng:
• Dòng đầu tiên chứa bốn số nguyên dương ~N~, ~M~, ~s~, ~t~ ~(1 \leq s, t \leq N, s \neq t)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số ~u_i~, ~v_i~, ~c_i~ thể hiện có đường hai chiều nối hai ngôi nhà ~u_i~ và ~v_i~, và độ dài là ~c_i~ (~u_i \neq v_i~).

Output

• Ghi ra hai dòng:
• Dòng đầu tiên ghi ra độ dài đường đi ngắn nhất.
• Dòng thứ hai là số hiệu trên đường đi ngắn nhất tìm được theo thứ tự di chuyển, bắt đầu từ ~s~ và kết thúc ở ~t~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N \leq 10^3, M \leq 2.10^3~
• Subtask ~2~ (~70\%~ số điểm): ~N \leq 10^5, M \leq 2.10^5~

Example

Sample input

3 3 1 3
1 2 3
1 3 5
2 3 1 

Sample output

4
1 2 3

Cho một đồ thị gồm ~n~ đỉnh và ~m~ cạnh có hướng có trọng số.

Với mỗi đỉnh ~i~, hãy tính độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ ~(1 \le u, v \le n, u \neq v)~, miêu tả cạnh gồm đỉnh ~u~ nối với đỉnh ~v~ có trọng số ~w~.

Output

• Gồm ~n-1~ dòng, dòng thứ ~i~ in ra độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i + 1~ và quay về đỉnh ~1~. Nếu không có quãng đường nào như vậy thì in ra ~-1~.

Constraints

• ~1 \le n,n \le 2*10^5~.
• ~1 \le w \le 10^9~.

Subtasks

• Subtask ~1~: Nếu tồn tại cạnh ~(u,v,w)~ thì sẽ có cạnh ~(v,u,w)~. ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 7
1 4 5
1 5 3
3 5 2
5 4 10
5 1 7
3 2 5
2 1 1

Sample Output 1:

-1
-1
-1
10

Sample Input 2:

2 1
2 1 10

Sample Output 2:

-1

Định nghĩa ~f(x)~ là tổng các chữ số của số nguyên ~x~. Cho số nguyên ~k~, hãy tìm giá trị ~f(x)~ nhỏ nhất có thể khi xét các số nguyên dương ~x~ chia hết cho ~k~.

Input

• Gồm một số nguyên ~2 \le k \le 100000~.

Output

• In ra giá trị ~f(x)~ nhỏ nhất.

Sample Test

Input:

6

Output:

3

Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1, 2, \ldots, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Metsälä.
• Sau này, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~ và ~c~: một chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và giá của nó là ~c~. Mỗi chuyến bay đều là một chiều.
• Bạn có thể giả định rằng luôn luôn có thể đi từ Syrjälä đến Metsälä.

Output

• In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
• Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là ~x~, giá tiền của nó trở thành ~\lfloor x/2 \rfloor~ (làm tròn xuống một số nguyên).

Constraints

• ~2 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

3 4
1 2 3
2 3 1
1 3 7
2 1 5

Sample output

2

Bạn dự định đi từ Syrjälä đến Lehmälä bằng máy bay. Bạn muốn tìm câu trả lời cho các câu hỏi sau:

• giá rẻ nhất của một lộ trình như vậy là bao nhiêu?
• có bao nhiêu lộ trình với giá rẻ nhất? (chia lấy dư cho ~10^9 + 7~)
• số lượng chuyến bay tối thiểu của một lộ trình với giá rẻ nhất là bao nhiêu?
• số lượng chuyến bay tối đa của một lộ trình với giá rẻ nhất là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và chuyến bay. Các thành phố được đánh số ~1, 2, \ldots, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Lehmälä.
• Sau này, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~, và ~c~: có một chuyến bay từ thành phố ~a~ đến thành phố ~b~ với giá ~c~. Tất cả chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có một lộ trình từ Syrjälä đến Lehmälä.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le m \le 2 \cdot 10^5~
• ~1 \le a,b \le n~
• ~1 \le c \le 10^9~

Example

Sample input

4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3

Sample output

5 2 1 2

Cho một đồ thị ~n~ đỉnh và không có cạnh. Có ~q~ truy vấn thuộc một trong hai loại sau:

• 1 u v thêm cạnh giữa ~u~ và ~v~.
• 2 u v kiểm tra liệu ~u~ và ~v~ có được kết nối với nhau không.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• ~q~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~t, u, v~, một truy vấn.

Output

• Với mỗi truy vấn loại 2, in ra YES nếu ~u~ và ~v~ kết nối với nhau, ngược lại in ra NO.

Điều kiện

• ~1 \le n, q \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

6 5
1 1 2
1 1 3
2 2 3
1 5 6
2 4 5

Output:

YES
NO

Cho một đồ thị ~n~ đỉnh và không có cạnh. Có ~q~ truy vấn thuộc một trong hai loại sau:

• 1 u v thêm cạnh giữa ~u~ và ~v~.
• 2 u tính tổng các đỉnh trong thành phần liên thông của ~u~.

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn. Nếu là truy vấn loại 1, một dòng gồm 3 số nguyên ~1, u, v~. Nếu là truy vấn loại 2, một dòng gồm 2 số nguyên ~2, u~.

Output

• Với mỗi truy vấn loại ~2~, in ra một số nguyên trên một dòng là tổng các đỉnh trong thành phần liên thông của ~u~.

Điều kiện

• ~1 \le n, q \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

6 5
1 1 2
1 1 3
2 2
1 5 6
2 4

Output:

6
4

Cho một đồ thị liên thông, vô hướng và có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Tìm trọng số của cây khung nhỏ nhất của đồ thị.

Cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị. Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• ~m~ dòng tiếp theo gồm 3 số nguyên ~u, v, w~, có cạnh trọng số ~w~ giữa ~u~ và ~v~.

Output

• In ra trọng số của cây khung nhỏ nhất.

Điều kiện

• ~1 \le n, m\le 10^5~.
• ~1 \le u, v \le n~.
• ~1 \le w \le 10^9~.

Ví dụ

Input:

3 3
1 2 1
2 3 2
3 1 3

Output:

3

Cho một dãy số ~a_1, a_2, ... a_N~. Một nghịch thế là một cặp số ~u, v~ sao cho ~u < v~ và ~a_u > a_v~. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

• Dòng đầu ghi số nguyên dương ~N~ ~(N \leq 10^5)~.
• Dòng sau gồm ~N~ số nguyên dương ~a_i~ ~( 1 ≤ a_i ≤ 10^5 )~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

3
3 1 2

Sample Output 1

2

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Ở một đất nước nọ, có ~n~ thành phố được kết nối với nhau bằng ~n-1~ con đường 2 chiều, đảm bảo rằng từ một thành phố bất kì có thể tới được tất cả các thành phố khác.

Thành phố thứ ~i~ có một giá trị ~a_i~, là độ "đẹp của thành phố đó. Các giá trị a_i này có thể giống nhau, tức là các thành phố có thể có độ đẹp ngang nhau.

Một vị khách du lịch khi tới đất nước này chơi trong ~k (1 \le k \le 10^{18})~ ngày. Hiện tại, vị khách ấy đang ở thành phố 1. Cách di chuyển của vị khách này rất đặc biệt, ví dụ ở ngày thứ i và vị khách đang ở thành phố ~u~ (ở ngày đầu thì anh ta ở thành phố 1), anh sẽ đi tới thành phố ~v~ khác ~u~, sao cho ~a_v - dist(u,v)~ là lớn nhất (~dist(u,v)~ là đường đi ngắn nhất từ thành phố ~u~ tới ~v~). Nếu có nhiều thành phố thỏa mãn điều kiện trên, anh ta sẽ đi tới thành phố có chỉ số nhỏ nhất.

Là một người yêu thích tin học, vị khách đưa ra một yêu cầu trước khi tham quan, đó là hãy tính xem, sau ~k~ ngày, anh ta sẽ ở thành phố nào. Hãy lập trình và giải bài toán này giúp anh ấy.

Input

• Dòng đầu gồm 2 số ~n~ và ~k~, lần lượt là số thành phố và số ngày vị khách ở ~(1 \le n \le 3 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng sau gồm ~n~ số miêu tả dãy ~a~. ~(0 \le a_i \le 10^9 \; \forall \; 1 \le i \le n).~
• ~n-1~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ miêu tả con đường 2 chiều nối ~u~ và ~v~.

Output

In ra thành phố mà anh ta sẽ đến sau ~k~ ngày.

Ràng buộc

• Subtask 1: ~n \le 1000, k \le 10^5~ (20%)
• Subtask 2: ~n \le 1000, k \le 10^{18}~ (15%)
• Subtask 3: ~n \le 300000, k \le 10^5~ (50%)
• Subtask 4: ~n \le 300000, k \le 10^{18}~ (15%)

Sample Test

Input:

5 4
1 1 3 2 4
1 2
1 3
2 4
2 5

Output:

5

Giải thích:

• Vị khách sẽ đi theo thứ tự 1 --> 3 --> 5 --> 2 --> 5

Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra ~m~ con búp bê của mình để thực hiện nhiệm vụ. Alice có ~n~ thùng đựng búp bê, thùng thứ ~i~ có ~a_i~ con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra ~m~ con búp bê.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m~ ~(1 \le m \le n \le 1000)~
• Dòng tiếp theo gồm ~n~ số tự nhiên là số lượng búp bê của từng thùng. (~1 \le a[i] \le 10^9~)

Output

• Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo ~10^9 + 7~

Sample Test

Input:

3 2
1 2 1

Output:

5

Giải thích:

• Có 5 cách chọn là: ~\{1, 2.1\}, \{1, 2.2\}, \{1, 3\}, \{2.1, 3\}, \{2.2, 3\}~ với ~x.y~ là con búp bê thứ ~y~ của thùng thứ ~x~

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

6 2 3 
1 5 
2 3 
3 4 
4 5 
5 6
1 2

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Vào một ngày đẹp trời, bỗng dưng Thinkies đi lạc vào một mê cung. Mê cung được biểu diễn dưới dạng một ma trận ~n*m.~ Ô hàng ~i~, cột ~j~ của mê cung được gọi là ô ~(i,j)~. Mê cung này rất đặc biệt, có ~p~ ô lối vào và ~q~ ô lối ra. Thinkies có thể xuất phát từ một ô bất kì trong ~p~ ô lối vào đó, và có thể thoát ra bằng cách đi tới một ô bất kì trong ~q~ ô lối ra. Mỗi ô đều chứa những giá trị riêng, ô ~(i,j)~ có giá trị ~a(i,j)~. Từ một ô ~(i,j)~ bất kì, Thinkies có thể di chuyển theo 2 cách (đều mất một đơn vị thời gian):

• Di chuyển sang ô kề cạnh với nó (từ ô ~(i,j)~ có thể tới ô ~(u,v)~ nếu ~(u,v)~ kề cạnh với ~(i,j)~ và ~a(u,v) \neq 0~).
• Sử dụng phép teleport, di chuyển sang ô ~(u,v)~ nếu ~u*v = a(i,j)~ và ~a(u,v) \neq 0~. Tuy nhiên, Thinkies chỉ có thể sử dụng được ~k~ lần phép teleport này mà thôi. Lưu ý, nếu trên các ô lối vào hoặc lối ra có giá trị a(u,v) = 0 thì ta sẽ không thể nào xuất phát hoặc đi vào ô đó. Hãy tìm cách đưa Thinkies ra khỏi mê cung sớm nhất có thể!

Input

• Dòng đầu gồm 3 số ~n,m,k (1 \le n, m \le 1000, k \le 3)~
• ~n~ dòng sau, mỗi dòng gồm m số ~a(i,j)~ biểu hiện mê cung
• Dòng tiếp theo gồm 2 số tự nhiên ~p,q (p+q \le n*m)~.
• ~p~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối vào.
• ~q~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối ra.

Output:

Số đơn vị thời gian ít nhất để Thinkies có thể ra khỏi mê cung, nếu không thể thoát ra in ra số ~-1~.

Ràng buộc

~a(i, j) \le 6 * 10 ^ 6~

• Subtask 1: ~n \le 50, m \le 50, k = 0~. (20%)
• Subtask 2: ~n \le 1000, m \le 1000, k = 0~. (30%)
• Subtask 3: ~n \le 50, m \le 50.~ (20%)
• Subtask 4: ~n,m \le 1000, k \le 3.~ (30%)

Sample Test 1

Input:

3 3 1
6 1 1
1 1 1
1 1 1
1 1
1 1
3 3

Output:

2

Sample Test 2

Input:

2 2 3
0 1 
2 1
1 1
1 1
2 1 

Output:

-1

Sample Test 3

Input:

2 2 3
2 1 
0 1
1 1
1 1
2 1 

Output

-1

Giải thích

• Ở test 2, do ô ~(1,1)~ có ~a(1,1) = 0~ nên ta không thể xuất phát từ ô đó, nên sẽ không thể đi ra.
• Ở test 3, do ô ~(2,1)~ có ~a(2,1) = 0~ nên ta không thể đi vào ô đó, nên không thể thoát ra mê cung.