Đất nước Mirinda tươi đẹp được mô tả bằng một ma trận ~n \times m~ ô vuông, ô ở dòng thứ ~i~ từ trên xuống và cột thứ ~j~ từ trái sang gọi là ô ~(i, j)~. Khoảng cách giữa ô ~(x,y)~ với ô ~(i,j)~ là ~|x - i| + |y - j|~. Ô ~(i, j)~ có giá trị tài sản là ~a_{i,j}~.

Do biến đổi khí hậu, những cơn bão ngày một nhiều hơn và mạnh hơn. Mỗi cơn bão được đặc trưng bởi:

• ~w~ - cấp bão,
• ~R_1~ - bán kính bão,
• ~R_2~ - bán kính mắt bão,
• ~(x, y)~ - tọa độ bão sẽ đổ bộ.

Theo đó, các ô ~(i, j)~ có khoảng cách đến ô ~(x, y)~ thuộc đoạn ~[R_2, R_1]~ sẽ bị tác động, đồng thời giá trị tài sản ở ô đó sẽ giảm đi min(w, b[i][j]), với ~b_{i,j}~ là giá trị tài sản hiện có ở ô ~(i, j)~.

Là một nước giáp biển, hằng năm đất nước Mirinda phải đón ~k~ trận bão. Do đặc trưng địa hình, bão sẽ chỉ đổ bộ vào một trong ~q~ ~(q < 5)~ điểm phân biệt. Rút kinh nghiệm từ siêu bão Fanta, ủy ban chống bão muốn biết sau khi ~k~ trận bão đó tàn phá thì nước này phải chịu tổng thiệt hại là bao nhiêu?

(Tổng thiệt hại của nước này được tính bằng tổng mức giảm giá trị tài sản của tất cả các ô).

Input

• Dòng đầu tiên chứa ~4~ số nguyên dương ~n,m,q,k~ (~1 < n, m < 500, k \leq 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ (~0 < a_{i,j} < 10^9~).
• Dòng tiếp theo ghi ~2 \times q~ số nguyên là tọa độ của ~q~ điểm đặc biệt: ~x_1, y_1, x_2, y_2, \ldots, x_q, y_q~.
• ~k~ dòng cuối, mỗi dòng ghi ~5~ số nguyên mô tả cơn bão: ~w, R_1, R_2, x, y~ (~0 < R_2 < R_1 < 1000, 0 < w < 1000~). Dữ liệu đảm bảo ~x,y~ là ~1~ trong ~q~ điểm đã cho.

(Các trận bão sẽ được liệt kê theo đúng thứ tự đổ bộ).

Output

In ra tổng thiệt hại sau ~k~ cơn bão.

Sample Test

Input:

3 4 2 4
10 11 12 15
20 10 11 25
30 32 35 40
1 1 3 4
2 2 0 3 4
2 2 0 1 1
2 4 2 1 1
2 3 1 3 4

Output:

56

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

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

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

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Cho một dãy ~A~ gồm ~n~ phần tử nguyên dương ~A_1, A_2, ..., A_n~.

Một dãy ~B~ được gọi là tương thích với dãy ~A~ khi và chỉ khi:

• ~B~ gồm ~n + 1~ phần tử nguyên dương.
• Với mọi ~1 \le i \le n~, ta có ~LCM(B_i, B_{i + 1}) = A_i~.

Ví dụ với dãy ~A= [2, 6]~ thì dãy ~B~ thoả mãn là ~B = [1, 2, 3]~.

Nhiệm vụ của bạn là đếm số dãy ~B~ thoả mãn với dãy ~A~ cho trước. Vì kết quả có thể rất lớn nên hãy in ra sau khi lấy ~mod~ với ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số số nguyên dương ~n~ ~(1 \le N \le 10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^6)~.

Output

• In ra số dãy ~B~ thoả mãn sau khi mod cho ~10^9 + 7~.

Scoring

• Có ~20\%~ số test có ~n \le 200~ và ~A_i \le 2000~.
• Có ~20\%~ số test có ~A_i = 2^k~ với ~k~ là một số nguyên không âm.
• Có ~30\%~ số test có ~A_i \le 5000~.
• Có ~30\%~ số test không có giới hạn gì thêm.

Sample Input 1

2
2 6

Sample Output 1

5

Sample Input 2

6
3 3 3 3 3 3

Sample Output 2

34

Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~.

Một "Tập Phủ Đỉnh" (Vertex Cover) là một tập đỉnh ~S~ sao cho với mọi cạnh ~(u, v) \in E~, ta luôn có ~u~ hoặc ~v~ thuộc ~S~. Gọi ~V(S)~ là giá trị của tập phủ đỉnh này, ~V(S)~ = chênh lệch nhỏ nhất giữa các index đỉnh của tập ~S~. Nói cách khác, nếu ~S~ bao gồm các đỉnh ~u_1, u_2, ..., u_k~, thì ~V(S) = min(|u_i - u_j|) (i \neq j)~.

Nhiệm vụ của bạn là tìm ra một tập phủ đỉnh sao cho ~V(S)~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 2 \times 10^5)~

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i, v_i~ miêu tả cạnh thứ ~i~.

Output

• In ra giá trị ~V(S)~ tìm được.

Sample Input 1

7 6

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

Sample Output 1

2

Sau khi không thể tiếp cận các chú mèo của Ivan Tèo, Khoi đã tới một nơi khác để hái nấm.

Các cây nấm cũng được mọc trên một cái cây gồm ~n~ đỉnh và ~n-1~ cạnh. Cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~ mang trọng số là ~w_i~. Mỗi nút sẽ chứa một cây nấm. Do là nấm hoang nên không có ai thuê robot MDuc canh gác, vậy nên Khoi có thể tới hái nấm bất cứ khi nào.

Vì sức lực có hạn, Khoi sẽ đi hái nấm trong ~q~ lần, lần hái thứ ~i~ cậu sẽ tới vào ngày ~d_i~ và khởi hành từ đỉnh ~u_i~ của cây, sau đó hái các cây nấm với khoảng cách không quá ~k_i~, biết rằng khoảng cách giữa hai đỉnh ~u~ và ~v~ là max trọng số các cạnh của đường đi ngắn nhất từ ~u~ tới ~v~.

Do không muốn Khoi quay lại bắt những chú mèo của mình, Ivan Tèo đã làm phép để cho sau khi bị hái, các cây nấm sẽ tự động sinh trưởng trở lại và sẽ mọc lại hoàn toàn trong ~X~ ngày nếu như nó không bị Khoi tới hái. Điều này có nghĩa, nếu cây nấm bị hái ở ngày ~d~ và trong ~X~ ngày sau đó nó không bị tìm đến lần nữa, thì ở ngày ~d+X~ nó sẽ mọc lại thành một cây nấm mới.

Khoi không để ý lắm tới điều này, vậy nên bạn hãy giúp Khoi tính được số nấm mà mình hái được trong mỗi lần nhé!

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 3 \times 10^5)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i, w_i~ ~(1≤u,v≤n; u≠v; w_i \le 10^9)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~ với độ dài ~w_i~.
• Dòng tiếp theo gồm hai số nguyên dương ~q~ và ~X~ miêu tả số lần hái nấm và số ngày để nấm mọc lại ~(q \le 3 \times 10^5, X \le 10^9)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên ~d_i,u_i,k_i~ miêu tả truy vấn thứ ~i~ ~(d_i \le 10^9, k_i \le 10^9)~.
• Các ~d_i~ tăng dần.

Output

• Với mỗi truy vấn, in ra số nấm mà Khôi hái được trong lần đó.

Subtask

• Subtask ~1~: ~n,q \le 2000 ~. ~(20\%)~
• Subtask ~2~: ~n \le 3\times 10^5~ và nút ~i~ nối với nút ~i+1~ trên cây. ~(30\%)~
• Subtask ~3~: ~X = 1~. ~(20\%)~
• Subtask ~4~: Không có giới hạn gì thêm. ~(30\%)~

Sample Input 1

3
1 2 4
3 1 7
3 3
4 2 7
6 1 15
15 2 3

Sample Output 1

3
0
1