Cho ma trận kích thước ~n \times m~. Hãy tìm ma trận con vuông ~k \times k~ có tổng lớn nhất.

Input

• Dòng đầu chứa ~3~ số nguyên ~n, m~ và ~k~ (~2 \leq k \leq n,m \leq 1000~) - kích thước ma trận và ma trận con.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ phân cách bởi dấu cách (~0 \leq a_{i,j} \leq 1000~).

Output

• In ra tổng của ma trận con ~k \times k~ có tổng lớn nhất.

Sample Test

Input:

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

Output:

11

Cho ma trận kích thước ~n \times m~ và một số nguyên ~k~.

Cho ~q~ truy vấn, mỗi truy vấn gồm ~4~ số ~(x, y, u, v)~. Với mỗi truy vấn, hãy đếm số phần tử bằng ~k~ nằm trong bảng con có góc bên trái phía trên là ô ~(x, y)~ và góc bên phải phía dưới là ô ~(u, v)~.

Input

• Dòng đầu chứa ~3~ số nguyên ~n, m~ và ~k~ (~2 \leq n, m \leq 1000, 1 \leq k \leq 10^9~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ phân cách bởi dấu cách (~0 \leq a_{i,j} \leq 1000~).
• Dòng thứ ~n+1~ chứa số nguyên ~q~ (~1 \leq q \leq 10^5~) - số lượng truy vấn.
• ~q~ dòng sau, mỗi dòng chứa bốn số nguyên ~x_i, y_i, u_i, v_i \ (1\le x_i \le u_i \le n, 1\le y_i \le v_i \le m, 1\le i\le q)~.

Output

• Kết quả gồm ~q~ dòng, dòng thứ ~i~ in ra kết quả của truy vấn ~i~.

Sample Test

Input:

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

Output:

1
0

Điều kiện thoả mãn dãy ngoặc đúng được định nghĩa như sau:

• Dãy rỗng "" là một dãy ngoặc đúng.
• Nếu dãy ~A~ là một dãy ngoặc đúng thì ~(A)~ là một dãy ngoặc đúng.
• Nếu dãy ~A~ và dãy ~B~ là hai dãy ngoặc đúng thì ~A + B~ là một dãy ngoặc đúng.

Cho xâu ~s~ là một dãy ngoặc chỉ gồm 2 kí tự là ~(~ và ~)~, hãy kiểm tra xem xâu ~s~ có phải một dãy ngoặc đúng hay không.

Input

• Gồm một dòng chứa xâu ngoặc ~s~ ~(1 \le |s| \le 10^3)~.

Output

• In ra Yes nếu xâu ~s~ là dãy ngoặc đúng, ngược lại in ra No.

Ví dụ

Input 1:

(()())

Output 1:

Yes

Input 2:

(()))

Output 2:

No

Cho mảng ~A~ gồm ~n~ phần tử ~a_1, a_2, \ldots, a_n~. Với mỗi phần tử ~i~ từ ~1~ đến ~n~, hãy tìm ~j~ sao cho ~j < i~ và ~a_j < a_i~ với ~i - j~ nhỏ nhất. Nói cách khác, với mỗi phần tử, hãy tìm phần tử gần nhất về phía bên trái nhỏ hơn nó.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~)
• Dòng thứ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots a_n~ (~1 \le a_i \le 10^9)~

Output

• Gồm một dãy ~n~ số, số ở vị trí ~i~ là vị trí phần tử gần nhất về bên trái của ~i~ mà có giá trị bé hơn ~a_i~. Nếu không tồn tại giá trị đó, in ra ~0~.

Sample Input 1

8
2 5 1 4 8 3 2 5

Sample Output 1

0 1 0 3 4 3 3 7

~ABC~ là một thầy giáo dạy toán nổi tiếng, đối với thầy, chỉ có hai loại số duy nhất là số nguyên tố và hợp số. Lớp học của thầy gồm ~n~ học sinh được đánh thứ tự từ ~1~ tới ~n~. Học sinh thứ ~i~ có mã số là ~a_i~ ~(1≤a_i≤3×10^5)~. Chú ý rằng ở đây các bạn học sinh không nhất thiết là có mã số khác nhau.

Một ngày nọ, thầy đến lớp và mang theo vô số viên kẹo. Thầy sẽ có ~q~ lượt phát kẹo, ở mỗi lượt thầy sẽ chọn một số nguyên dương ~t~ ~(1≤t≤2)~ và ba số nguyên dương ~l,r,v (1≤l≤r≤n; 1≤ v≤10^9)~. Thầy sẽ đi phát cho tất cả các bạn học sinh có số thứ tự ~i~, sao cho ~i∈[l,r]~, đúng ~v~ viên kẹo mỗi bạn. Tuy nhiên, thầy bỗng thấy cách chia kẹo này không thú vị, và quyết định rằng nếu ~t=1~, thầy sẽ chỉ phát kẹo cho các bạn thỏa mãn điều kiện vừa rồi đồng thời mã số ~a_i~ của bạn ấy là số nguyên tố. Ngược lại, nếu ~t=2~, thầy sẽ chỉ đi phát kẹo cho các bạn với mã số ~a_i~ là hợp số.

Sau ~q~ lượt phát kẹo, thầy muốn biết mỗi bạn học sinh có số kẹo là bao nhiêu. Do thầy chỉ dạy toán chứ không phải tin, thầy muốn nhờ các bạn lập trình tính hộ số kẹo của từng bạn.

Lưu ý ở đây ta tạm coi ~1~ là hợp số.

Input

-Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1≤ n,q≤10^5)~; -Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,…,a_n~ miêu tả mã số học sinh từ ~1~ tới ~n~. -~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~t,l,r,val (1 \le t \le 2; 1≤l \le r≤10^5; 1 \le val≤10^9)~.

Output

• In ra một dòng ~n~ số nguyên dương là số kẹo của từng bạn học sinh.

Subtask

• Có ~20\%~ số test tương ứng với số điểm có ~n,q \le 100~
• Có ~30\%~ số test khác tương ứng với số điểm có ~n,q \le 10^4~
• Có ~30\%~ số test còn lại tương ứng với số điểm có: ~a_i~ đều là số nguyên tố.
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

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

Output 1

1 2 1 2 2 1

Giải thích 1

Ở lượt đầu tiên, ta chỉ phát kẹo cho các học sinh trong đoạn ~[2,5]~ với mã số là số nguyên tố, đó là ba bạn thứ ~2,4,5~.

Ở lượt thứ hai, ta phát kẹo cho các bạn trong đoạn ~[1,6]~ với mã số là hợp số, đó là các vị trí ~1,3,6~.

Ở lượt thứ ba, ta không thể phát kẹo cho bạn thứ ~5~ vì mã số của bạn là ~7~, đó không phải hợp số.

Trong kì thi học sinh giỏi, mrtee phải chuẩn bị ~N~ máy tính cho ~N~ học sinh tham gia dự thi. ~N~ máy tính được xếp thẳng hàng nhau trên trục hoành của trục số, máy thứ ~i~ có toạ độ ~x_i~. Khoảng cách của hai máy ~i~ và ~j~ được tính là ~|x_i - x_j|~. Để đảm bảo nghiêm túc trong thi cử, thầy giáo muốn đặt một camera quan sát học sinh thẳng hàng với các máy trên sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Yêu cầu: Hãy giúp thầy giáo xác định số vị trí đặt camera sao cho tổng khoảng cách từ camera đến các máy tính là nhỏ nhất.

Input

• Dòng đầu tiên chứ số nguyên dương ~N~ (~N \leq 10^6~).
• Dòng thứ hai gồm ~N~ số nguyên ~x_1, x_2, \ldots, x_N~ - toạ độ các máy tính (~|x_i| \leq 10^9~).

Output

• Dòng đâu tiên in ra số ~K~ - số vị trí đặt camera thoả mãn.
• Dòng thứ hai in ra các toạ độ đặt thoả mãn được sắp theo thứ tự tăng dần, cách nhau ít nhất một khoảng trắng.

Subtasks

• ~50\%~ số test ứng với ~N \leq 10^3~.
• ~50\%~ số test ứng với ~N \leq 10^5~.

Sample Test

Input:

6
3 1 7 2 5 7

Output:

3
3 4 5

Cho hai số ~n, k~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp có độ dài không nhỏ hơn ~k~ của dãy ~a~ có trung bình cộng lớn nhất.

Input

• Dòng đầu gồm 2 số nguyên ~n, k~ ~(1 < k \le n \le 2*10^5)~;
• Dòng sau gồm ~n~ số nguyên mô tả dãy ~a~ ~(|a_i| \le 10^9)~.

Output

• In ra một số thực duy nhất là giá trị trung bình cộng lớn nhất thỏa mãn. Kết quả lấy ~3~ chữ số sau dấu phẩy.

Sample Test

Input

4 3
17 0 14 1

Output

10.333

Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~. Tìm đoạn con liên tiếp dài nhất có tổng không âm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~ (~|a_i| \leq 10^9)~.

Output

In ra độ dài đoạn con thoả mãn. Nếu không tồn tại đoạn con thoả mãn in ra -1.

Subtasks

• Subtask ~1~ (~50\%~): ~n \leq 10^3~.
• Subtask ~2~ (~50\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5
-1 -1 2 -2 -3

Output:

3