Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy tìm một đoạn con ~[l, r]~ ~(1 \le l \le r \le n)~ của dãy ~a~ sao cho đoạn con đó có tổng lớn nhất.

Input

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

Output

Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input:

5
1 3 -2 3 -5

Output

5

Đường Hà Nội có ~n~ cái cột đèn được đánh số từ ~1~ đến ~n~. Tuy nhiên, trận bão tàn khốc vừa qua đã khiến ~t~ ~(t \leq n)~ cây đèn này bị đổ.

Sắp tới thầy Tùng cần tổ chức một lễ hội ẩm thực tại đây, và yêu cầu cần tổ chức tại nơi có ít nhất ~k~ cái đèn còn nguyên vẹn liên tiếp. Vì thời gian gấp rút, bạn được thầy yêu cầu tìm xem cần phải sửa chữa ít nhất bao nhiêu cây đèn để có thể tổ chức lễ hội.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, k, t~ ~(1 \le t, k \le n \le 10^5)~.
• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương là vị trí có cây đèn bị đổ.

Output

• In ra một số nguyên duy nhất là số cây đèn cần được sửa chữa.

Sample Test

Input:

10 6 5
2
10
1
5
9

Output:

1

Note:

Sửa cây đèn tại vị trí ~5~ và chọn các cây ~3, 4, 5, 6, 7, 8~ để tổ chức lễ hội.

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l < r \le n)~ sao cho ~a_l + a_{l+1} + ... + a_r~ chia hết cho ~d~

Input

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

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 4
1 3 -2 3 -5

Sample Output

4

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l \le r \le n)~ sao cho trung bình cộng của đoạn con ~[l, r]~ là ~k~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, |k| \le 10^6)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^6 \le a_i \le 10^6)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 2
1 3 -2 3 -5

Sample Output

1

Cho một bảng ~n \times m~, mỗi ô ~(i, j)~ của bảng được gán một giá trị riêng biệt ~a_{i, j}~. Bạn được yêu cầu trả lời ~q~ truy vấn, mỗi truy vấn gồm bốn số nguyên dương ~u, v, x, y~ tương đương với việc bạn cần tìm tổng các giá trị nằm trong bảng con có góc trái trên là ô ~(u, v)~ và góc phải dưới là ô ~(x, y)~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 1000)~.
• ~n~ dòng tiếp tiếp, mỗi dòng gồm ~m~ số nguyên dương ~a_{i, j}~ là các giá trị của các ô trong bảng. ~(a_{i, j} \le 10^9)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~u, v, x, y~ ~(1 \le u \le x \le n, 1 \le v \le y \le m)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là đáp án của kết quả truy vấn thứ ~i~.

Sample Input

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

Sample Output

18
54
5
18

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Bạn được phép thay đổi bất kì một số trong dãy trên thành một số nguyên dương khác bất kì. Hãy tìm cách thay đổi tối ưu để ước chung lớn nhất của dãy trên lớn nhất có thể, hay ~gcd(a_1, a_2, ..., a_n)~ là lớn nhất.

Input

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

Output

• Gồm một số nguyên duy nhất là kết quả bài toán.

Sample Input

3
4 3 8

Sample Output

4

Note

Có thể thay đổi ~a_2=3~ thành ~a_2 = 16~. Từ đó ~gcd(a_1, a_2, a_3) = gcd(4, 16, 8) = 4~.

Cho một dãy xâu ~S~ gồm ~n~ kí tự từ ~1~ đến ~9~. Hãy đếm số lượng cặp ~(i, j)~ ~(1 \le i \le j \le n)~ thỏa mãn các chữ số trong đoạn ~[i, j]~ tạo thành một số nguyên chia hết cho ~2023~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài xâu ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ kí tự của xâu ~S~.

Output

Gồm số nguyên duy nhất là kết quả bài toán.

Sample Test

Input:

10
2427624276

Output:

3

Note

Các cặp ~(i, j)~ thỏa mãn là: ~(1, 5)~ ~(6, 10)~, ~(1, 10)~.

Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

• Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.
• Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ của bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Constraint

• ~1 \le n \le 400~.
• ~-10^6 \le b_i, a_i \le 10^6~.

Input

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

Output

• In ra ~S~ lớn nhất tìm được.

Subtask

• ~30\%~ số test có ~n \le 10~
• ~40\%~ số test có ~n \le 50~.
• ~30\%~ số test có ~n \le 400~.

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Explanation 1

• Chọn đoạn ~[1,5]~ và ~[2,5]~.