Từ dãy số tự nhiên ~1; 2; 3; ...; N~ người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên ~K~ là ước nào đó của ~N~ như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho ~K~;
• Đoạn thứ hai gồm tất cả các sổ chia ~K~ dư 1;
• Đoạn thứ ba gồm tất cả các số chia ~K~ dư 2;
• ...
• Đoạn cuối cùng gồm tất cà các số chia ~K~ dư ~K~ - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với ~N = 12~ và ~K = 4~ sau khi sắp xếp ta có dãy số sau: ~4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11~

Yêu cầu: Cho trước 3 số nguyên dương ~N; K; M~ (với ~K~ là ước của ~N~ và ~M < N~). Tìm số hạng thử ~M~ của dãy đã sắp xếp.

Input

• 3 số nguyên dương ~N; K; M~ (~N \le 10^{16}; K \le 10^9; K~ là ước của ~N~; ~M < N~) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

• Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Scoring

• Có 20% test ứng với ~N \le 10^2~;
• Có 30% test ứng với ~10^2 < N \le 10^6~;
• Có 30% test ứng với ~10^6 < N \le 10^9~;
• Có 20% test ứng với ~10^9 < N \le 10^{16}~.

Sample Tests

Input

12 4 6

Output

9

Trong cuộc thám hiểm gần đây, bạn đã phát hiện ra một hầm kho báu có thể được biểu diễn dưới dạng lưới với ~N~ hàng (được đánh số từ ~1~ đến ~N~) và ~M~ cột (được đánh số từ ~1~ đến ~M~). Ô ở hàng ~r~ và cột ~c~ được ký hiệu là ~(r, c)~. Ô ~(r, c)~ chứa kho báu nếu ~A_{r,c} = 1~, và ô đó trống nếu ~A_{r,c} = 0~.

Có ~Q~ kịch bản độc lập. Đối với mỗi kịch bản, bạn bắt đầu ở ô ~(R, C)~ và bạn muốn mang chính xác ~K~ kho báu trở về ô ~(R, C)~. Trong một giây, bạn có thể di chuyển đến bất kỳ ô nào kề bên theo hướng ngang, dọc hoặc chéo với ô bạn đang đứng, như được minh họa trong hình dưới đây. Do kho báu rất lớn, bạn chỉ có thể mang mỗi lần một kho báu, nghĩa là bạn phải mang kho báu trở về ô ~(R, C)~ trước khi lấy kho báu tiếp theo hoặc để hoàn thành kịch bản. Hành động nhặt hoặc bỏ kho báu không tốn thời gian.

Đối với mỗi kịch bản, xác định thời gian tối thiểu cần thiết (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~. Vì tất cả các kịch bản đều độc lập với nhau, nên sau mỗi kịch bản, các kho báu sẽ được trở lại vị trí ban đầu.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 1000~).
• Mỗi dòng trong ~N~ dòng tiếp theo bao gồm một chuỗi nhị phân ~A_i~ có độ dài ~M~. Ký tự thứ ~j~ của chuỗi ~A_i~ mô tả ô ~(i, j)~: là ~1~ nếu ô ~(i, j)~ chứa kho báu và là ~0~ nếu ô ~(i, j)~ trống. Số lượng kho báu trong hầm ít nhất là một.
• Dòng tiếp theo chứa một số nguyên ~Q~ (~1 \leq Q \leq 2 \times 10^4~).
• Mỗi dòng trong ~Q~ dòng tiếp theo gồm ba số nguyên ~R~, ~C~ và ~K~ (~1 \leq R \leq N~; ~1 \leq C \leq M~; ~1 \leq K~) mô tả mỗi kịch bản. Giá trị của ~K~ không vượt quá số lượng kho báu trong hầm.

Output

• Đối với mỗi kịch bản, xuất ra một số nguyên trên một dòng riêng biệt biểu thị thời gian tối thiểu (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~.

Sample

Input 1

5 5
11000
01011
10111
00101
10010
6
1 1 1
1 2 4
3 1 13
1 4 5
2 5 3
3 3 8

Output 1

0
8
64
16
4
20

Input 2

1 6
000111
3
1 1 2 
1 1 1
1 6 3

Output 2

14
6
6

Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có ~m~ hàng và ~n~ cột. Các hàng của bảng được đánh số từ ~1~ tới ~m~ từ trên xuông dưới, các cột của bảng số được đánh số từ ~1~ tới ~n~ từ trái qua phải. Giá trị của số nằm ở hàng ~i~ cột ~j~ được kí hiệu là ~a(i,j)~. Cần thực hiện lần lượt ~Q~ thao tác, thao tác thứ ~t~ ~(1 \le t \le Q)~ được mô tả bằng bộ năm số ~x_t,y_t,u_t,v_t,c_t~, thao tác này sẽ tăng tất cả các phần tử ~a(i,j)~ với mọi ~x_i \le i \le u_t, y_t \le j \le v_t~ lên một lượng là ~c_t~ ~(c_t > 0)~.

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả ~Q~ thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện ~Q~ thao tác. Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện ~Q-1~ thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy ~Q~ thao tác, gọi ~W_t~ là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ ~t~ ~(1 \le t \le Q)~, tính ~Min(\{W_1,W_2,...,W_Q\})~.

Input

• Dòng đầu chứa hai số nguyên dương ~n,m~ .
• ~n~ dòng sau, dòng thứ ~i~ gồm ~n~ số nguyên không âm ~a(i,1), a(i,2), ..., a(i,n)~.
• Dòng tiếp theo chứa số nguyên dương ~Q~.
• Tiếp theo là ~Q~ dòng, dòng thứ ~t~ gồm ~5~ số nguyên dương ~x_t,y_t,u_t,v_t,c_t~.

Điều kiện

• ~1 \le n \times m \le 10^6~
• ~1 \le Q \le 10^6~
• ~a(i,j) \le 10^9~.
• ~c_i \le 10^3~.

Output

Gồm một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.

Ví dụ

Input

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

Output

3

Thạch đang ở một trò chơi đặc biệt trong khu vui chơi. Đó là một mê cung có dạng bảng hình chữ nhật, có kích thước ~m \times n~ (~m~ dòng, ~n~ cột). Trong này có ~k~ ô chứa vật cản. Ô nằm ở hàng ~i~, cột ~j~ được kí hiệu là ô ~(i,j)~.

Vào thời điểm ban đầu, Thạch đứng ở ô ~(1,1)~. Tại mỗi lượt, cậu chỉ được đi xuống dưới hoặc sang phải. Dĩ nhiên, Thạch không được phép đi vào ô có vật cản. Mục tiêu của trò chơi là đi tới ô đích ở ~(m,n)~.

Tuy nhiên, điểm đặc biệt ở mê cung này là: Mọi vật cản đều di chuyển theo mỗi bước chân của Thạch (có lẽ là do sân này có gắn cảm biến và nhiều cỗ máy đặc biệt chăng?). Quy luật như sau:

• Sau khi đi xuống dưới một hàng thì mọi vật cản dịch lên trên ~1~ đơn vị, riêng những vật cản ở dòng ~1~ bây giờ sẽ được đẩy "lên" dòng cuối ~m~
• Nếu đi qua phải thì mọi vật cản dịch sang trái ~1~ đơn vị, riêng những vật nằm trên cột ~1~ sẽ được đẩy sang cột cuối ~n~.
• Nói cách khác, các vật cản dịch chuyển theo vòng tròn.
• Sau một bước đi bất kì của Thạch, nếu có vật cản nào đó dịch tới chỗ cậu đang đứng thì Thạch sẽ bị loại khỏi mê cung và coi như thua cuộc (kể cả sau khi bước tới ô đích).

Việc giành chiến thắng có vẻ quá đơn giản với một gamer như Thạch. Vì thế điều cậu ấy đang quan tâm hơn hết là: Đếm số cách khác nhau để cậu có thể đi tới được đích đến tại vị trí ~(m,n)~, chia lấy dư cho ~2004010501~.

Bạn hãy lập trình giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa ba số ~m,n,k (0 \le k \le m \times n, 1 \le m,n \le 1000)~
• ~m~ dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài ~n~. Nếu kí tự thứ ~j~ trên dòng thứ ~i~ là "#", ô ~(i,j)~ là ô chứa vật cản. Ngược lại, nếu là "." thì ô ~(i,j)~ là ô trống.
• Dữ liệu đảm bảo có đúng ~k~ ô "#" trong mê cung, và ô ~(1,1)~ lúc đầu không chứa vật cản.

Output

Một dòng duy nhất chứa đáp án

Scoring

Bộ test được chia thành ~4~ phần như sau:

• Subtask 1 (~25\%~ số điểm): ~m + n \le 20~
• Subtask 2 (~25\%~ số điểm): ~k = 0~
• Subtask 3 (~15\%~ số điểm): ~n = 2~
• Subtask 4 (~35\%~ số điểm): không có ràng buộc gì thêm

Example

Sample input 1

2 3 1
...
..#

Sample output 1

2

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3