Cho số nguyên dương ~n~, hãy tìm số nguyên ~m~ nhỏ nhất sao cho ~m!~ có ít nhất ~n~ chữ số ~0~ ở cuối.

Input:

• Dòng đầu tiên: chứa số nguyên ~T~ (~1 ≤ T ≤ 10^5~ ) là số test
• ~T~ dòng tiếp theo: mỗi dòng chứa một số nguyên ~n~ (~1 ≤ n ≤ 10^{16}~).

Output :

• Gồm ~T~ dòng, dòng thứ ~i~ chứa kết quả của truy vấn thứ ~i~.

Scoring

• Có 50% số test ứng ~n ≤ 10^5,T=1~
• Có 50% số test còn lại không có ràng buộc gì thêm

Sample Input 1

2
1
3

Sample Output 1

5
15

Số chính phương là số tự nhiên có căn bậc 2 là một số tự nhiên, hay nói cách khác, số chính phương có thể biểu diễn dưới dạng bình phương (lũy thừa bậc 2) của một số tự nhiên. Ví dụ: 4 là số chính phương, vì ~4=2^2~ ; 9 là số chính phương, vì ~9=3^2~.

Bờm rất thích các số chính phương, muốn tìm hiểu về nó, và biết rằng số chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên phân biệt. Chẳng hạn: ~9=1 \times 9~; ~144=2 \times 3 \times 4 \times 6~. Bờm hay ngẫm nghĩ về nó mọi lúc khi có thời gian rảnh. Hôm nay, giờ giải lao trên lớp, Bờm quay sang đố Tuấn: "Với số tự nhiên ~N~ cho trước, tìm số chính phương lớn nhất bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số từ 1 đến ~N~". Tuấn suy nghĩ mãi mà chưa trả lời được câu đố mà thời gian thì ít quá.

Yêu cầu: Cho một số nguyên ~N~, hãy giúp Tuấn đưa ra số chính phương lớn nhất bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số từ 1 đến ~N~. Số đó có thể rất lớn nên chỉ cần xuất ra phần dư khi chia số đó cho 1000000007 ~(10^9 + 7)~.

Input

• Một dòng duy nhất chứa số nguyên dương ~N~ ~(N \leq 4 \times 10^4­)~.

Output

• Ghi ra một dòng duy nhất là kết quả bài toán sau khi đã ~mod~ ~1000000007~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N \leq 10^2~.
• Subtask ~2~ (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask ~3~ (~40\%~ số điểm): ~N \leq 4 \times 10^4~.

Sample Input 1

5 

Sample Output 1

4

Cho một hoán vị ~P = (p_1; p_2; … ;p_n)~ của tập hợp ~\{1; 2; … ; 𝑛\}~ và một số nguyên ~k~. Với mỗi số nguyên ~i = k; k + 1; … ; n~, hãy in ra giá trị lớn thứ ~k~ trong dãy con ~(p_1; … ;p_i)~. Chú ý: Giá trị lớn thứ ~𝐾~ trong một dãy là giá trị ở vị trí thứ ~k~ (đánh số vị trí từ ~1~) của dãy sau khi đã được sắp xếp giảm dần. Ví dụ, với dãy ~(1; 3; 2)~; ~k = 3~; sau khi sắp xếp giảm dần, dãy trở thành ~(3; 2; 1)~, giá trị lớn thứ ~3~ của dãy là ~1~.

Dữ liệu

• Dòng ~1~: chứa hai số nguyên ~𝑛, 𝐾 (1 ≤ 𝐾 ≤ 𝑛 ≤ 500 000)~;
• Dòng ~2~: chứa 𝑛 số nguyên ~p_1; p_2; … ;p_n~ là một hoán vị của ~\{1; 2; … ; 𝑛\}~.

Kết quả

• Ghi trên ~n - k + 1~ dòng, mỗi dòng là câu trả lời tương ứng với ~i = k, k + 1, … , n~.

Giới hạn

• Subtask ~1~: ~18\%~ số điểm có ~𝑛 = 2~;
• Subtask ~2~: ~22\%~ số điểm có ~𝑝_1 > 𝑝_2 > ⋯ > 𝑝_𝑛~;
• Subtask ~3~: ~20\%~ số điểm có ~𝑛 ≤ 1000~;
• Subtask ~4~: ~25\%~ số điểm có ~𝑛 ≤ 8000~;
• Subtask ~5~: ~15\%~ số điểm còn lại không có thêm ràng buộc bổ sung.

Sample Input 1

2 1
1 2

Sample Output 1

1
2

Explannation 1

• Với ~i=2~, giá trị lớn thứ hai trong dãy ~(1; 3)~ là ~1~;
• Với ~i=3~, giá trị lớn thứ hai trong dãy ~(1; 3; 2)~ là ~2~;

Sample Input 2

3 2
1 3 2

Sample Output 2

1
2

Explannation 2

• Với ~i=2~, giá trị lớn thứ hai trong dãy ~(1; 3)~ là ~1~;
• Với ~i=3~, giá trị lớn thứ hai trong dãy ~(1; 3; 2)~ là ~2~;

Công ty Long Vân đang sản xuất robot vận chuyển hàng hóa tự động. Để làm việc đó, công ty tiến hành huấn luyện các robot trên một địa hình được chia thành một lưới các ô vuông gồm ~𝑚~ dòng (đánh số từ 1 đến ~𝑚~ theo chiều từ trên xuống dưới) và ~𝑛~ cột (đánh số từ 1 đến ~n~ theo chiều từ trái sang phải). Ô giao giữa dòng ~i~, cột ~j~ được gọi là ô (~i, j~), có độ cao là ~ℎ_{𝑖𝑗}\ (|ℎ_{𝑖𝑗}| \le 10^9)~ và có điểm thưởng là ~𝑠_{𝑖𝑗}\ (|𝑠_{𝑖𝑗}| \le 10^9)~.

Một thử nghiệm cho robot như sau: Đặt robot ở một ô nào đó, điểm thưởng của robot bằng điểm thưởng tại ô được đặt, mỗi bước robot được phép dừng lại hoặc di chuyển sang ô chung cạnh có độ cao cao hơn độ cao của ô hiện tại. Khi robot di chuyển sang ô nào đó, điểm thưởng của robot được cộng một lượng là điểm thưởng tại ô đó.

Yêu cầu: Cho địa hình thử nghiệm robot, hãy tìm vị trí đặt robot và cách di chuyển của robot để khi robot dừng lại, tổng điểm thưởng của robot là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~𝑚, 𝑛~;
• Tiếp theo là ~𝑚~ dòng mô tả độ cao của các ô trên địa hình, dòng thứ ~𝑖~ chứa ~𝑛~ số ~ℎ_{𝑖1}, ℎ_{𝑖2}, … , ℎ_{𝑖𝑛}~;
• Tiếp theo là ~𝑚~ dòng mô tả điểm thưởng của các ô trên địa hình, dòng thứ ~𝑖~ chứa ~𝑛~ số ~𝑠_{𝑖1}, 𝑠_{𝑖2}, … , 𝑠_{𝑖𝑛}~.

Output

• Một dòng chứa một số là tổng điểm nhiều nhất mà robot có thể đạt được.

Scoring

• Subtask #1 (~20\%~ số điểm): ~𝑚 = 1; 𝑛 \leq 10^3~
• Subtask #2 (~20\%~ số điểm): ~𝑚 = 1; 𝑛 \leq 10^5~;
• Subtask #3 (~20\%~ số điểm): ~𝑚 \times 𝑛 \leq 10^3~ và ~𝑠_{𝑖𝑗} = 1~;
• Subtask #4 (~20\%~ số điểm): ~𝑚 \times 𝑛 \leq 10^5~ và ~𝑠_{𝑖𝑗} = 1~;
• Subtask #5 (~20\%~ số điểm): ~𝑚 \times 𝑛 \leq 10^5~

Example

Input

3 4
1 2 3 4
4 5 5 7
8 7 6 5
1 1 1 1
1 1 1 1
1 1 1 1

Output

7

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~.

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.

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%)