Thành phố của Bình có nhiều con đường được trồng cây xanh. Mỗi cây xanh được đặt tên bằng một chữ cái latinh hoa. Theo Bình, một đoạn đường được gọi là xanh đẹp nếu đoạn đường đó chỉ trồng một loại cây xanh (tức là trên đoạn đường đó, các cây được trồng ở vị trí liên tiếp, có tên giống nhau và thuộc một con đường).

Yêu cầu: Hãy giúp Bình tìm đoạn đường xanh đẹp gồm nhiều cây xanh nhất trong tất cả các con đường của thành phố.

Input

• Dòng ~1~ ghi số nguyên dương ~N (N \le 100)~ là số con đường trong thành phố.
• ~N~ dòng tiếp theo, mỗi dòng ghi một xâu kí tự gồm các chữ cái latinh hoa mô tả tên của các cây xanh được trồng liên tiếp từ đầu con đường đến cuối con đường. Số lượng cây trên mỗi con đường không lớn hơn ~10^4~.

Output

• In ra một số nguyên là số lượng cây xanh trên đoạn đường xanh đẹp gồm nhiều cây xanh nhất trong các con đường của thành phố.

Subtask

• Có ~80\%~ số test ứng với ~0 < N \le 10~ và số cây trên mỗi con đường không quá ~100~.
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
ABBBABAAH
HHHHHAHHHA
EEAE

Sample Output 1

5

Explanation 1

• Đoạn đường xanh đẹp gồm nhiều cây nhất là ~5~ cây ~(HHHHH)~ trong con đường thứ ~2~.

Chúng ta đã quá rõ việc một số nguyên tố (prime) là số nguyên dương lớn hơn ~1~ có duy nhất hai ước là ~1~ và chính nó. Để làm mới bài toán, hôm nay, ta sẽ định nghĩa một số TPrime là một số nguyên dương lớn hơn ~1~ gồm đúng ~3~ ước.

Cho ~n~ truy vấn, mỗi truy vấn là một số ~a~, hãy kiểm tra xem số này có phải là số TPrime hay không.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 3*10^5)~
• ~n~ dòng sau, mỗi dòng gồm một số nguyên dương ~a~ ~(1 \le a \le 10^{12})~ miêu tả truy vấn.

Output

• In ra ~n~ dòng, với mỗi truy vấn, nếu ~a~ là số TPrime thì in ra "YES", ngược lại in ra "NO".

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100, 1 \le a \le 10^4~
• Có ~30\%~ số test ứng với ~1 \le n,a \le 10^5~
• Có ~50\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
4
6
7

Sample Output 1

YES
NO
NO

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.

Hãy đếm số đoạn con liên tiếp ~[l,r]~ của dãy ~a~ sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay ~a_l + a_{l+1} + ... + a_r = r - l + 1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.

Output

• In ra số đoạn con thỏa mãn.

Điều kiện

• ~1 \le n \le 2*10^5~.
• ~0 \le a \le 9~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 2*10^5~.

Ví dụ

Input 1:

3
1 2 0

Output 1:

3

Input 2:

5
1 1 0 1 1 

Output 2:

6

Trên dãy số nguyên ~a_1,a_2,...,a_n~ và với hai số nguyên ~w_1,w_2~, ta định nghĩa một bộ năm chỉ số ~1 \le i_1 < i_2 < ... < i_5 \le n~ được gọi là bộ năm và có trọng số được tính bằng: ~(w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_3 + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5})~.

Ví dụ, trên dãy gồm ~7~ số nguyên ~2,8,1,9,1,-1,8~ và ~w_1 = 1~, ~w_2 = -1~ thì bộ năm chỉ số ~2,3,4,6,7~ là một bộ năm có trọng số bằng ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times (-1)) + (1 \times 8) =25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số ~a_1,a_2,...,a_n~ và hai số nguyên ~w_1~ và ~w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,w_1,w_2~ ~(5 \le n \le 10^5; |w_1|, |w_2| \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output

• Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100~
• Có ~20\%~ số test ứng với ~w_1 = w_2 = 0~
• Có ~20\%~ số test ứng với ~n \le 5000, w_1 = 0~
• Có ~20\%~ số test ứng với ~w_1 = 0~
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

25

Sample Input 2

7 0 0
2 8 1 9 1 -1 8

Sample Output 2

9

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Đấ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

Bài giảng về quy hoạch động được minh họa bằng bài toán tìm đường đi trên lưới ô vuông như sau. Cho lưới ô vuông hình chữ nhật có ~m~ dòng và ~n~ cột. Mỗi ô ~(i,j)~ của lưới có ghi một số nguyên ~a_{ij}~, với ~(i \in [1,m], j \in [1,n])~. Từ mỗi ô chỉ có thể di chuyển sang ô kề cạnh bên phải hoặc xuống dưới (nếu tồn tại ô đến). Giá trị đường đi là tổng các số ghi trên những ô nằm trên đường đi. Hãy tìm đường đi có giá trị lớn nhất, xuất phát từ ô đầu bên trái và kết thúc ở ô dưới bên phải. Đường đi này được gọi là đường đi tối ưu.

Bài giảng trên được mở rộng và nâng cao ở buổi ngoại khóa cho học sinh giỏi. Một loạt các test được tạo ra để kiểm tra chương trình của học sinh. Xây dựng test mới là một việc khó và buồn tẻ. Vì vậy thầy giáo thông báo là sử dụng các test cũ đã có, nhưng ở mỗi test giá trị một ô bị thay đổi thành số cực nhỏ (có thể bằng ~0~ hoặc âm) để đường đi tối ưu không còn được như cũ và giá trị đường đi tối ưu mới sẽ là giá trị nhỏ nhất trong các khả năng giá trị một ô bị thay đổi. Ô trên trái và ô dưới phải vẫn giữ nguyên giá trị cũ. Hình vẽ sau minh họa cho ví dụ ở dưới.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~m~ và ~n~ ~(2 \le n,m \le 1500)~.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên miêu tả ma trận ~a~.

Output

• Ghi ra một số nguyên dương duy nhất là giá trị đường đi tối ưu mới.

Subtask

• Có ~60\%~ số test ứng với ~2 \le m,n \le 50~.
• Có ~20\%~ số test ứng với ~2 \le n,m \le 300~.
• ~20\%~ số test còn lại không giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

17