Ví dụ:

Input1:

2 4 3

Output1:

-1

Input2:

2 7 3

Output2:

5

Trên một màn hình lớn, người ta lần lượt cho xuất hiện các số của một dãy gồm 𝑛 số nguyên ~𝑎_1,𝑎_2,…,𝑎_𝑛~ và cứ lặp đi lặp lại như thế (nghĩa là sau khi ~𝑎_𝑖~ xuất hiện vài giây đến lượt ~𝑎_𝑖+1~ xuất hiện, số xuất hiện sau ~𝑎_𝑛~ là ~𝑎_1~).

Yêu cầu: Hãy đếm số lượng số âm của 𝑘 số xuất hiện liên tiếp trên màn hình bắt đầu từ lần thứ xuất hiện thứ ~𝑚~.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên ~𝑛~,~𝑘~,~𝑚~.
• Dòng 2: Ghi ~𝑛~ số nguyên ~𝑎_𝑖~.

Dữ liệu ra:

• Ghi số nguyên dương là số lượng số âm tìm được.

Ví dụ:

Input:

5 7 2
-56 56 -41 35 4

Output:

3

Giới hạn dữ liệu:

~𝑛<10^3~; ~𝑘<10^9~; ~𝑎_𝑖<10^6~

Trong bộ test có:

• 40% test có ~𝑚+𝑘≤𝑛~

• 40% test có ~𝑚+𝑘< 10^7~

Trên một màn hình lớn, người ta lần lượt cho xuất hiện các số của một dãy gồm 𝑛 số nguyên ~𝑎_1,𝑎_2,…,𝑎_𝑛~ và cứ lặp đi lặp lại như thế (nghĩa là sau khi ~𝑎_𝑖~ xuất hiện vài giây đến lượt ~𝑎_𝑖+1~ xuất hiện, số xuất hiện sau ~𝑎_𝑛~ là ~𝑎_1~).

Yêu cầu: Hãy đếm số lượng số dương của 𝑘 số xuất hiện liên tiếp trên màn hình bắt đầu từ lần thứ xuất hiện thứ ~𝑚~.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên ~𝑛~,~𝑘~,~𝑚~.
• Dòng 2. Chứa ~𝑛~ số nguyên ~𝑎_𝑖~.

Dữ liệu ra:

• Ghi số nguyên dương là số lượng số dương tìm được.

Ví dụ:

Input:

5 7 9
3 -5 7 -8 6

Output:

4

Giới hạn dữ liệu:

~𝑛<10^3~; ~𝑘<10^9~; ~𝑎_𝑖<10^6~

Trong bộ test có:

• 40% test có ~𝑚+𝑘≤𝑛~

• 40% test có ~𝑚+𝑘< 10^7~

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. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số đó có bao nhiêu số nguyên tố. 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.

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 in ra số lượng các số nguyên tố 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^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à số lượng các số nguyên tố từ ~x~ đến ~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

2
2
2

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số nguyên tố. Ví dụ: Cho N=10, x=3, y =6, dãy số từ 1 đến 10. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 2 số nguyên tố là: 3 và 5.

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

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~.
• ~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 (~0≤x \le y \le N,q≤10^6~).

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ố nguyên tố từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

10 3
1 3
3 6
3 7

Output

2
2
3

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ố đó). Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số phong phú. Ví dụ: Cho N=13, x=3, y =12, dãy số từ 1 đến 13. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 12 có tất cả 1 số phong phú là: 12.

Yêu cầu: Cho số nguyên ~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~ .
• ~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 (~0≤x \le y \le N,q≤10^6~).

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
3 13
3 7

Output

0
1
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

Số T-Prime là số có đúng 3 ước. Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số T-Prime. Ví dụ: Cho N=40, x=3, y =30, dãy số từ 1 đến 40. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 30 có tất cả 2 số T-Prime là: 9 và 25.

Yêu cầu: Cho số nguyên dương ~N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số T-Prime từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1 ≤ N \le 10^7~, ~q≤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≤ x \le y \le 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ố T-Prime từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

40 3
1 3
1 30
3 10

Output

0
3
2

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. 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 số đó. 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 3 số trên 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 in ra tổng các số nguyên tố từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^6~) 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 (~1 ≤ x \le y \le 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ố từ ~x~ đến ~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

Một nhà khoa học đang nghiên cứu một dải năng lượng bí ẩn trải dài qua nhiều điểm, mỗi điểm được đánh dấu bằng một giá trị năng lượng ~A_i~ (có thể là dương hoặc âm). Họ muốn chọn một đoạn liên tục trong dải này để thu thập năng lượng tối đa.

Nhà khoa học có một thiết bị thu năng lượng hình chữ nhật với kích thước ~2~ x ~k~ (với ~k ≥ 2~ tùy ý). Thiết bị này có thể thu thập năng lượng từ bất kỳ đoạn nào trên dải, nhưng phải đảm bảo thiết bị nằm hoàn toàn trong phạm vi của dải.

Yêu cầu: Hãy giúp nhà khoa học tìm ra vị trí đặt thiết bị sao cho tổng năng lượng thu được là lớn nhất.

Dữ liệu vào:

• Dòng 1 chứa số nguyên dương ~N~ (~4 ≤ N ≤ 10^6~) - số lượng điểm trên dải năng lượng.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2,…, A_N~ (~|A_i| ≤ 10^9~ với ~1 ≤ i ≤ N~) - giá trị năng lượng tại mỗi điểm.

Dữ liệu ra:

• Gồm một số nguyên duy nhất là tổng năng lượng lớn nhất có thể thu được từ một đoạn mà thiết bị có thể bao phủ.

Ví dụ:

Input

6
-4 3 -2 -6 7 2

Output

2

Giải thích:

• Đoạn thu được năng lượng cao nhất

3 -2

7 -6

• Tổng năng lượng thu được từ đoạn này là: 3+ (-2) + 7 + (-6) = 2.

Ràng buộc:

• Subtask 1: Có 30% điểm tương ứng với trường hợp ~4 ≤ N ≤ 300~.
• Subtask 2: Có 30% điểm tương ứng với trường hợp ~300 < N ≤ 5000~.
• Subtask 3: Có 40% điểm tương ứng với trường hợp ~5000 < N ≤ 10^6~.

Cho dãy số nguyên dương A gồm N phần tử ~A_i~ (~1 \le i \le N~; ~3 \le N \le 10^6~; ~1 \le A_i \le 2.10^9~) và biểu thức ~M = A_i – 3A_j + 2A_k~ với ~A_i~, ~A_j~, ~A_k~ thuộc dãy số A (~1 \le i < j < k < N~).

Yêu cầu: Tìm giá trị M lớn nhất.

Input:

• Dòng 1: Ghi số nguyên dương N.
• Dòng 2: Ghi N số nguyên dương ~Ai~, mỗi số cách nhau một khoảng trống.

Output:

• Dòng 1: Ghi ra số M tìm được.

Example:

Input:

5
8 1 2 6 3

Output:

17

Constraints:

• Có 70% số lượng bộ test tương ứng với ~3 < N \le 300~; ~1 \le A_i \le 65535~
• Có 30% số lượng bộ test tương ứng với ~300 < N \le 10^6~; ~1 \le A_i \le 2.10^9~

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 - A_j - A_k~ sao cho S đạt giá trị lớn nhất.

Input:

Được cho bởi tệp relaxmax.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 relaxmax.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.

Example

Input

9
95 5 74 65 89 62 3 2 37 

Output

280

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= A_i - A_j + A_k~ sao cho S đạt giá trị lớn nhất.

Input:

Được cho bởi tệp upmax.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 upmax.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.

Example

Input

5
2 3 5 7 -3

Output

6

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 một dãy gồm ~N~ số nguyên đánh số từ 1 đến N (~A_1, A_2,…, A_N; |a_i| ≤ 10^9~) và được sắp xếp thành một vòng tròn theo chiều kim đồng hồ.

Yêu cầu: Hãy tìm tổng lớn nhất ~K~ số liên tiếp trong vòng tròn trên.

Dữ liệu vào:

• Dòng 1. Ghi 2 số nguyên dương ~N, K~ (~0 < K < N ≤ 10^5~) cách nhau một dấu cách.
• Dòng 2. Chứa ~N~ số nguyên là các phần tử ~A_i~ của dãy, mỗi số có giá trị tuyệt đối không vượt quá ~10^6~, giữa các số cách nhau một dấu cách.

Dữ liệu ra:

• Dòng 1: Ghi số nguyên duy nhất là tổng lớn nhất của ~K~ số liên tiếp nhau tìm được trong vòng tròn số.

Ví dụ

Input

5 3
10 2 3 5 7

Output

22

Ràng buộc:

• 50% số test: ~0 ≤ K< N ≤ 10^4~ ;
• 50% số test: ~10^4 < K < N ≤ 10^5~ ;

Trên một màn hình lớn, người ta lần lượt cho xuất hiện các số của một dãy gồm 𝑛 số nguyên không âm ~𝑎_1,𝑎_2,…,𝑎_𝑛~ và cứ lặp đi lặp lại như thế (nghĩa là sau khi ~𝑎_𝑖~ xuất hiện vài giây đến lượt ~𝑎_𝑖+1~ xuất hiện, số xuất hiện sau ~𝑎_𝑛~ là ~𝑎_1~).

Yêu cầu: Hãy tính tổng của 𝑘 số xuất hiện liên tiếp trên màn hình bắt đầu từ lần thứ xuất hiện thứ ~𝑚~.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên ~𝑛~,~𝑘~,~𝑚~.
• Trong ~𝑛~ dòng sau, dòng thứ ~𝑖~ chứa số ~𝑎_𝑖~.

Dữ liệu ra:

• Ghi giá trị tổng tìm được.

Ví dụ:

Input:

3 7 5 
2 
3 
6

Output:

25

Giới hạn dữ liệu:

~𝑛<10^3~; ~𝑘<10^9~; ~𝑎_𝑖<10^6~

Trong bộ test có:

• 40% test có ~𝑚+𝑘≤𝑛~

• 40% test có ~𝑚+𝑘< 10^6~

Cho một bảng gồm N hàng, M cột. Các hàng của bảng được đánh số từ 1 đến N từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến M từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j) và trên đó chứa một số nguyên dương là A[i, j] (~1 ≤ i, j ≤ N~)

Yêu cầu: Ứng với mỗi bộ (~h1,c1~) và (~h2,c2~) cho trước hãy tính và in ra tổng tất cả các ô nằm trên hình chữ nhật được tạo bởi giao giữa hàng ~h1~, cột ~c1~; hàng ~h2~, cột ~c2~.

Dữ liệu vào:

Cho trong file tonghcn.inp có cấu trúc như sau:

• Dòng 1: Ghi hai số nguyên dương ~N~, ~M~ (~1 ≤ N ≤ M ≤ 10^3~ ).
• Dòng thứ i trong N dòng tiếp theo: Ghi ~M~ số nguyên dương, số thứ j là ~A[i, j]~ (~A[i, j] ≤ 10^3~).
• Dòng thứ N+2: Ghi số nguyên dương T là số lượng bộ test cần tìm (~T ≤ 10^3~.
• T dòng tiếp theo mỗi dòng ghi 4 số nguyên dương ~h_1, h_2, c_1, c_2~.

Dữ liệu ra:

Ghi ra file tonghcn.out với cấu trúc như sau:

• Gồm T dòng, mỗi dòng ghi tổng tìm được ứng với T test đã cho.

Ví dụ:

Input

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

Output

21
10

Cho một mảng gồm ~n~ số nguyên và số nguyên ~t~.

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá ~t~. Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

• Dòng thứ nhất chứa hai số nguyên ~n~,~t~(~1≤n≤10^5;1≤t≤10^9~)
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~(~1≤a_i≤10^4~)

Output

In ra giá trị cần tìm. Example Test 1

Input

4 4
1 2 1 2

Output

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 lưới ô vuông ~A~ kích thước ~N~ x ~N~. Các dòng được đánh số 1 đến ~N~ từ trên xuống dưới, các cột được đánh số 1 đến ~N~ từ trái qua phải. Ô nằm trên giao giữa dòng ~i~ và cột ~j~ được gọi là ô (~i,j~) và trên đó có ghi một số nguyên dương ~A_{ij}~ (~1 ≤ i, j ≤ N~).

Yêu cầu: Hãy lập trình chọn một ô vuông con có kích thước ~K~ x ~K~ có tổng giá trị của tất cả các ô của hình vuông con là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương ~N~, ~K~ (~N ≤ 10^3~, ~K ≤ N~).

• Dòng thứ i trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên dương, số thứ j là ~A_{ij}~ (~A_{ij} ≤ 10^3~)

Dữ liệu ra:

• Một số nguyên dương là tổng giá trị lớn nhất theo yêu cầu đề ra.

Ví dụ:

Input

4 3 
1 9 1 1 
9 9 9 9 
1 9 9 9 
1 9 9 14 

Output

86

Ràng buộc:

• Có 70% số test ~N<10~ và ~k<10~.
• Có 30% test còn lại không có ràng buộc gì thêm