Cho một mảng ~a~ gồm ~n~ số nguyên, hãy tìm đoạn con liên tiếp dài đúng ~L~ có tổng lớn nhất.

• Một đoạn con dài ~L~ là [~a_i, a_{i+1}, ..., a_{i+L-1}~] với ~1 ≤ i ≤ n-L+1~
• Tính tổng lớn nhất của tất cả các đoạn con dài đúng ~L~.

Input

• Dòng 1: hai số nguyên ~n~ và ~L~ (~1 ≤ L ≤ n ≤ 2×10^5~)
• Dòng 2: mảng ~a[1] a[2] … a[n]~, mỗi phần tử ~-10^9 ≤ a[i] ≤ 10^9~

Output

• Một số nguyên: tổng lớn nhất của đoạn dài ~L~

Ví dụ

Input1:

5 3
1 2 3 1 2

Output1:

6

Giải thích:

Các đoạn dài 3:

[1,2,3] → tổng = 6

[2,3,1] → tổng = 6

[3,1,2] → tổng = 6

→ Tổng lớn nhất = 6

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Nam đố Quân bài toán sau: Cho dãy số gồm ~N~ số nguyên dương, các số trong dãy được đánh số bắt đầu từ 1. Tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy đã cho. Ví dụ: Cho N=7, x=3, y =6, dãy số 3, 6, 2, 17, 11, 22, 19. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 3 số nguyên tố là: 2, 17, 11; nên tổng các số nguyên tố có trong đoạn từ 3 đến 6 là: 30

Yêu cầu: Cho dãy gồm có ~N~ số nguyên, ứng với mỗi cặp số ~x~, ~y~ hãy tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^7~) các số cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên.

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy trên.

Ví dụ:

Input

7 3
1 3 5 6 8 9 11
1 3
2 6
3 7

Output

8
8
16

Cho một mảng a gồm n số nguyên, các phần tử có thể âm, dương hoặc bằng 0.

• Một đoạn con là dãy liên tiếp [~a_l, a_{l+1}, …, a_r~] với ~1 ≤ l ≤ r ≤ n~.
• Tính số đoạn con sao cho tổng = ~K~.

Nhiệm vụ: đếm số đoạn con có tổng bằng ~K~.

Input

• Dòng 1: ~n~ — số phần tử trong mảng (~1 ≤ n ≤ 2×10^5~)
• Dòng 2: ~a[1] a[2] … a[n]~ — mảng số nguyên: ~-10^9 ≤ a[i] ≤ 10^9~
• Dòng 3: ~K~ — tổng cần tìm, ~-10^{14} ≤ K ≤ 10^{14}~

Output

• Một số nguyên: số đoạn con có tổng bằng ~K~

Ví dụ

Input:

5
1 2 1 3 2
3

Output:

3

Giải thích:

Các đoạn con có tổng = 3:

[1,2] → tổng = 3

[2,1] → tổng = 3

[3] → tổng = 3

Hôm qua Bờm mới học về số tự kỷ (số tự kỷ là một số tự nhiên có tổng các ước thực sự nhỏ hơn nó). Ví dụ: ~N=8~ là một số tự kỷ vì N có tổng các ước thực sự: 1 + 2 + 4 = 7 < 8. Sau khi làm xong bài đếm số lượng các số tự kỷ trong đoạn từ a đến b (~a ≤ b~), Bờm nghĩ ra bài toán như sau: Với một số nguyên dương ~k~ biết trước, khi độ dài d (~1 ≤ d ≤ b - a + 1~) nhỏ nhất là bao nhiêu để với mọi đoạn con độ dài d của đoạn [~a, b~] đều có ít nhất ~k~ số tự kỷ. (Một đoạn con độ dài ~d~ của đoạn [~a~, ~b~] bắt đầu từ ~c~ (~a ≤ c ≤ b - d + 1~) gồm các số ~x, x + 1, ..., x + d - 1~).

Yêu cầu: Hãy giúp Bờm tìm giá trị của ~d~.

Dữ liệu vào: Đọc từ tệp văn bản DOANSTK.INP gồm một dòng duy nhất ghi ba số a, b, k cách nhau một dấu cách (~1 ≤ a ≤ b~, ~1 ≤ k ≤ 10^6~).

Kết quả: Ghi ra tệp văn bản DOANSTK.OUT một số duy nhất d, nếu không có d ghi -1.

Ví dụ:

Input1:

2 4 3

Output1:

3

Input2:

2 7 3

Output2:

4

Cho dãy gồm N ~(1 \le N \le 10^5)~ số nguyên ~A_1, A_2, A_N; (0 < A_i \le 10^5)~. Với bộ ba số (i,j,k) trong đó ~1 \le i < j < k \le N~ hãy tìm giá trị ~S= 2A_i + A_j + 3A_k~ sao cho S đạt giá trị nhỏ nhất.

Input:

Được cho bởi tệp lowmax.inp có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên ~A_1, A_2,..., A_N~ giữa các số cách nhau một khoảng trắng.

Output:

Được cho bởi tệp lowmax.out có cấu trúc như sau:

• In ra một số duy nhất là số S nhỏ nhất tìm được.

Example

Input

9
5 4 4 4 1 4 6 8 7

Output

15

Cho dãy gồm N ~(1 \le N \le 10^5)~ số nguyên ~A_1, A_2, A_N; (0 < A_i \le 10^5)~. Với bộ ba số (i,j,k) trong đó ~1 \le i < j < k \le N~ hãy tìm giá trị ~S= 3A_i + 2A_j - 5A_k~ sao cho S đạt giá trị lớn nhất.

Input:

Được cho bởi tệp three.inp có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên ~A_1, A_2,..., A_N~ giữa các số cách nhau một khoảng trắng.

Output:

Được cho bởi tệp three.out có cấu trúc như sau:

• In ra một số duy nhất là số S lớn nhất tìm được.

Yêu cầu:

Cho 1 dãy số nguyên gồm ~n~ số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú trong đoạn từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Giải thích:

• Ước thực sự của 1 số là tập hợp tất cả các ước dương nhỏ hơn nó.
• Số chính phương là số có căn bậc 2 của nó là một số nguyên.
• Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
• Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số 6 có tổng các ước số (không kể 6) là 1 + 2 + 3 = 6. Do đó 6 là một số hoàn hảo.
• Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.

Input:

• Dòng 1: Ghi số nguyên ~𝑛~, (~1 \le n \le 10^5~).
• Dòng 2: Ghi ~𝑛~ số nguyên ~A_1, A_2,...,A_n, 1 \le A_i \le 10^6~
• Dòng 3: Ghi số nguyên dương ~q~ - số bộ test.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le n~; ~1 \le q \le 10^5~)

Output:

• Gồm q dòng: Ứng với mỗi cặp số x,y in ra 4 số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú tìm được trong đoạn từ ~x~ đến ~y~.

Example:

Input:

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

Output:

0 3 0 0
0 3 0 0

Số phong phú là số có tổng các ước thực sự lớn hơn số đó (ước thực sự của 1 số là các ước nhỏ hơn số đó).

Yêu cầu: Cho số nguyên dương ~N~ và dãy gồm ~N~ số nguyên ~a_1, a_2, a_3,..., a_N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số phong phú từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^6~).
• Dòng 2: ghi N số nguyên ~a_1, a_2, a_3,..., a_N~ (~1 \le a_i \le 10^5~)
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên (~1 \le x \le y ≤ N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số phong phú từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

13 3
1 3 4 2 5 6 7 8 10 9 13 12 11
1 3
3 13
3 7

Output

0
1
0