Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~N~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~1~ tới phần tử thứ ~i~ là bao nhiêu ~( a_1, a_2, ..., a_{i-1}, a_i )~

Input

• Hai số nguyên là ~N(1 \leq N \leq 10^5)~, đại diện cho số phần tử của mảng ~A~
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.

Output

• Gồm ~N~ số nguyên ~a_i~ đại diện cho tổng các số từ ~1~ tới ~i~

Sample Input

4
1 2 3 4

Sample Output

1 3 6 10

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~1~ tới phần tử thứ ~x~ là bao nhiêu ~( a_1, a_{1+1}, ..., a_{x-1}, a_x )~

Input

• Số nguyên là ~N (1 \leq N \leq 10^5)~, đại diện cho số phần tử của mảng ~A~.
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
• Số nguyên ~Q (1 \leq Q \leq 10^5)~, là số lượng câu hỏi.
• Và ~Q~ dòng tiếp theo gồm 1 số nguyên duy nhất ~x( 1 \leq x \leq N)~, đại diện cho truy vấn từ ~1~ tới ~x~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

3
1 2 3
2
3
2

Sample Output

6
3

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~L~ tới phần tử thứ ~R~ là bao nhiêu ~( a_l, a_{l+1}, ..., a_{r-1}, a_r )~

Input

• Hai số nguyên là ~N, Q(1 \leq N, Q \leq 10^5)~, đại diện cho số phần tử của mảng ~A~ và số truy vấn
• Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
• Và ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R( 1 \leq L \leq R \leq N,)~, đại diện cho truy vấn từ ~L~ tới ~R~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

3 2
1 2 3
1 2
1 3

Sample Output

3
6

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~L~ tới phần tử thứ ~R~ là bao nhiêu ~( a_l, a_{l+1}, ..., a_{r-1}, a_r )~

Input

• Một số nguyên duy nhất là ~T (1 \leq T \leq 5)~ testcase và ~T~ khối tiếp theo gồm:
  • Hai số nguyên là ~N, Q(1 \leq N, Q \leq 10^5)~, đại diện cho số phần tử của mảng ~A~ và số truy vấn
  • Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
  • Và ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R( 1 \leq L \leq R \leq N,)~, đại diện cho truy vấn từ ~L~ tới ~R~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

5
6
5

Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng hai chiều ~A~ có ~N \times M~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số trong hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~ là bao nhiêu

Input

• Hai số nguyên là ~N, M(1 \leq N, M \leq 10^3)~, đại diện cho số hàng và số cột của mảng ~A~
• Dòng tiếp theo gồm ~N~ hàng và mỗi hàng có ~M~ phần tử ~a_{i,j}( 1 \leq i \leq N, 1 \leq j \leq M, 1 \leq a_{i,j} \leq 10^9 )~ của mảng ~A~.
• Dòng tiếp theo có duy nhất 1 số nguyên ~Q~, đại diên cho số truy vấn
• Và ~Q~ dòng tiếp theo với mỗi dòng gồm 4 số nguyên ~x_1, y_1, x_2, y_2( 1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M )~, đại diện cho truy vấn hình chữ nhật từ phần tử thứ ~(x_1,y_1)~ tới phần tử thứ ~(x_2,y_2)~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

18

Cho một mảng gồm ~n~ số nguyên dương, nhiệm vụ của bạn là đếm số lượng mảng con liên tiếp có tổng các phần tử chính xác bằng ~x~.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 2 \times 10^{5} ; 1 \le x \le 10^{9})~ ~-~ số lượng phần tử trong mảng và mục tiêu tổng ~x~.

Dòng tiếp theo gồm ~n~ số nguyên ~a_{1}, a_{2},..., a_{n}~ ~(1 \le a_{i} \le 10^{9})~ ~-~ giá trị của các phần tử trong mảng đã cho.

Output

Một số nguyên duy nhất là số lượng mảng con đếm được.

Sample Input

5 7
2 4 1 2 7

Sample Output

3

Giải thích

Có ~3~ mảng con thỏa mãn, đó là: ~[1, 3], [2, 4], [5, 5]~.

Hôm nay là ngày đầu tiên Luna và Tina hẹn hò. Luna quyết định mua hoa tặng Tina. Trong cửa hàng hoa có ~N~ bông hoa xếp theo hàng ngang, bông hoa thứ ~i~ từ trái sang có ~A_i~ cánh hoa. Để tiết kiệm thời gian, Luna quyết định mua một dãy các bông hoa liên tiếp trong cửa hàng để tạo thành một bó hoa. Ngoài ra, để bó hoa không quá đơn điệu, Luna muốn trong bó hoa có đúng ~K~ bông hoa có lẻ cánh hoa. Vì có quá nhiều cách chọn, Luna đang rất phân vân không biết nên chọn như thế nào.

Bạn là một trong những nhân viên của cửa hàng, hãy giúp Luna đếm số cách chọn bó hoa.

Input

Dòng đầu chứa hai số nguyên ~N~ và ~K~ ~(1 \leq K \leq N \leq 99999)~.

Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ là ~A_i~ ~(1 \leq A_i \leq 9^9)~.

Output

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

Simple Input

4 2
1 3 2 3

Simple Output

3

Cho một dãy số gồm ~n~ phần tử ~a_1,a_2,...a_n~ và ~q~ truy vấn ~l~, ~r~ ~(1 \le l \le r \le n)~. Yêu cầu kiểm tra tổng trong đoạn ~[l;r]~ có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^{3})~. Độ dài của mảng và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...a_n~ ~(1 \le a[i] \le 10^{3})~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l~, ~r~ , tương ứng với truy vấn thứ ~i~. Yêu cầu kiểm tra tổng từ ~[l;r]~ có phải là số nguyên tố hay không?

Output

• In ra ~q~ dòng tương ứng với câu trả lời thứ ~i~. In YES nếu tổng là số nguyên tố, ngược lại in NO.

Sample Input 1

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

Sample Output 1

NO
YES
YES
NO

Cho một dãy số gồm ~n~ phần tử ~a_1,a_2,...a_n~ và ~q~ truy vấn ~l~, ~r~ ~(1 \le l \le r \le n)~. Yêu cầu kiểm tra tổng trong đoạn ~[l;r]~ có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n \le 10^{4}; 1 \le q \le 10^{6})~. Độ dài của mảng và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...a_n~ ~(1 \le a[i] \le 10^{3})~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l~, ~r~ , tương ứng với truy vấn thứ ~i~. Yêu cầu kiểm tra tổng từ ~[l;r]~ có phải là số nguyên tố hay không?

Output

• In ra ~q~ dòng tương ứng với câu trả lời thứ ~i~. In YES nếu tổng là số nguyên tố, ngược lại in NO.

Sample Input 1

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

Sample Output 1

NO
YES
YES
NO

(Trích đề thi phỏng vấn Senior Dev lương 2000$)

Có một dãy ~n~ bóng đèn đánh số từ ~1~ đến ~n~ được nối với nhau thành một dãy. Có ~n~ thao tác: trong thao tác thứ ~i~ sẽ cho biết số thứ tự của bóng đèn được bật công tắc trong lần thứ ~i~. Biết rằng một bóng đèn được bật công tắc thì chưa hẳn nó sẽ sáng, cần phải có tất cả các bóng đèn có số thứ tự nhỏ hơn nó cũng đều được bật công tắc thì mới đảm bảo (theo nguyên lý mạch điện mắc nối tiếp). Yêu cầu đặt ra là đếm số thời điểm mà mọi bóng đèn được bật thì đều sáng.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Dòng tiếp theo là ~n~ số nguyên dương phân biệt có giá trị từ ~1~ đến ~n~ sắp xếp theo thứ tự nào đó, cho biết số thứ tự của các bóng đèn được bật.

Output

Đáp số của bài toán.

Sample input

5
2 1 3 5 4

Sample output

3

Giải thích: ta thấy lần đầu thì dù bóng đèn số 2 được bật, nhưng bóng 1 chưa bật thì bóng 2 vẫn chưa sáng; đến lần tiếp theo thì bóng 1 đã được bật thì cả 2 bóng 1, 2 đều sáng, tính một lần. Cứ thế, ta thấy các bóng sẽ sáng ngay thời điểm bật bao gồm: ~2, 3, 5.~

Mô tả

Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~. Với mỗi truy vấn, bạn cần tính tổng các số nguyên tố trong đoạn ~[L,R]~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ ~-~ số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~.

Output

Gồm ~Q~ dòng, mỗi dòng ứng với mỗi truy vấn, in ra một số duy nhất là tổng các số nguyên tố trong đoạn ~[L,R]~.

Ví dụ

Input

3
1 10
5 15
1 5

Output

17
36
10

Giải thích

• Truy vấn 1: Các số nguyên tố trong đoạn ~[1,10]~ là ~2, 3, 5, 7~. Tổng ~= 17~.
• Truy vấn 2: Các số nguyên tố trong đoạn ~[5,15]~ là ~5, 7, 11, 13~. Tổng ~= 36~.
• Truy vấn 3: Các số nguyên tố trong đoạn ~[1,5]~ là ~2, 3, 5~. Tổng ~= 10~.

Cho mảng A gồm n phần tử. Hãy cho biết có bao nhiêu đoạn con liên tiếp có tổng chia hết cho x.

Input

Dòng đầu tiên gồm 2 số n và x (~ 1 \le n \le 10^5 , 1 \le x \le 10^9 ~).

Dòng thứ hai gồm n số nguyên ~A_1, A_2, ..., A_n~ (~ 1 \le a_i \le 10^9 ~) các phần tử của mảng A.

Output

Một dòng duy nhất là số đoạn con liên tiếp có tổng chia hết cho x.

Examples

Input

6 3
5 1 2 4 3 2 

Output

9 

Giải thích: Các đoạn con liên tiếp có tổng chia hết cho 3 là:

• [1, 2]
• [1, 4]
• [1, 5]
• [2, 3]
• [2, 6]
• [3, 4]
• [3, 5]
• [4, 6]
• [5, 5]

Trong vùng đất H32 Da Poet.

Cáo trắng là một loại sinh vật nguy hiểm.

Vào ngày bình thường Cáo trắng ăn cắp bit của người dân để làm thức ăn. Nhưng vào những ngày trăng tròn, nếu Cáo trắng ăn cắp và ăn lượng bit có tổng trung bình là ~k~ của những dãy nhà người dân liên tục thì sức mạnh của Cáo trắng sẽ chẳng thể ngờ tới, sinh ra ảo giác và sẽ tấn công người dân. Vào lúc này nếu ai đó cho Cáo trắng một chai "vokka mâm xôi" thì nó sẽ trở lại bình thường.

Lo ngại an nguy cho các thần dân của mình. Nhà vua đã ra lệnh cho nhà toán học Lazyman tính toán xem có bao nhiêu dãy nhà liên tiếp có tổng trung bình lượng bit là ~k~ để có cách ngăn chặn con quái thú này.

Do bận với việc phải đi thực tập nên nhà toán học Lazyman đã nhờ đến bạn.

Input

Dòng đầu tiên chưa 2 số nguyên ~n~ và ~k~ ~(1 \leq k \leq 10)~ tương ứng với chiều dài và chiều rộng của vương quốc và lượng bit ~k~.

Dòng thứ hai, chứa ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ ~(-10 \leq a_i \leq 10)~ là số lượng bit ở nhà dân vị tri thứ ~i~ tương ứng.

OutputFile

Số lượng dãy bit liên tiếp có tổng trung bình là ~k~.

Simple Input

6 2
1 1 2 3 1 1

Simple Output

4

Giải thích test đề:

4 dãy nhà được chọn trong testcase trên là:

• 2
• 3 1
• 1 2 3
• 2 3 1

Cách tính điểm

• Subtest 1: (~50\%~ số điểm) Với ~n = 5~.
• Subtest 2: (~20\%~ số điểm) Với ~n = 1000~.
• Subtest 3: (~30\%~ số điểm) Với ~n = 1000000~.

Vào đợt khai giảng năm học mới, CLB lập trình có ra chiến dịch tuyển thành viên theo cách sau đây: mỗi SV muốn tham gia thì cần thi 3 bài: lập trình C/C++, kiểm tra tư duy logic và kiểm tra tiếng Anh. Điểm của mỗi người sẽ là ba số nguyên dương không vượt quá 1 tỷ. Với điểm thi ở một môn nào đó của một thí sinh ~X~ bất kỳ, ta định nghĩa "độ thua kém" so với thí sinh ~Y~ (cũng ở môn đó) là số điểm mà ~Y~ hơn ~X~, trong trường hợp ~X~ cao điểm hơn ~Y~ thì độ thua kém là ~0.~

Ví dụ: ở môn lập trình C/C++, nếu ~X~ đạt 7đ, ~Y~ đạt 9đ còn ~Z~ đạt 6đ thì ~X~ thua kém ~Y~ là 2đ nhưng thua kém ~Z~ là 0đ.

Tuy nhiên, bài kiểm tra là rất khó và hầu như các bạn đạt điểm rất thấp, không như mong muốn của CLB. Vì thế CLB đã đề xuất ra một khóa huấn luyện cho "thành viên dự bị" với chi phí được tính như sau: với mỗi ứng viên ~X~, chi phí mà ~X~ cần nộp bằng với giá trị lớn nhất của tổng độ thua kém ở cả ba môn so với từng ứng viên còn lại (đọc thêm VD minh họa để hiểu rõ hơn).

Bạn Vuvuzela, một thủ quỹ của CLB, muốn dựa vào kết quả thi của các thành viên, tính ra xem số tiền ít nhất và nhiều nhất mà các ứng viên cần nộp là bao nhiêu. Hãy giúp Vuvuzela thực hiện điều này nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 2 \cdot 10^5.~

Trong ~n~ dòng tiếp theo, mỗi dòng là một bộ ba điểm thi của các ứng viên.

Output

Số tiền nhiều nhất, ít nhất mà một ứng viên phải đóng.

Các subtasks trong bài:

• Có 50% điểm ứng với ~n \le 2023~ và các điểm số không vượt quá ~10^3.~
• Có 50% điểm ứng với ~2024 \le n \le 2 \cdot 10^5~ và các điểm số không vượt quá ~10^9.~

Sample input

3
6 7 8 
5 10 5
8 8 8

Sample output

6 2

Giải thích: Ta tính được chi phí mà các ứng viên phải đóng lần lượt là:

• Độ thua kém của 1 so với 2 là: ~0+3+0=3~; so với 3 là ~2+1+0=3~ nên chi phí là ~\max(3,3)=3~.
• Độ thua kém của 2 so với 1 là: ~1+0+3=4~; so với 3 là ~3+0+3=6~ nên chi phí là ~\max(4,6)=6~.
• Độ thua kém của 3 so với 1 là: ~0+0+0=0~; so với 2 là ~0+2+0=2~ nên chi phí là ~\max(2,2)=2~.

Do đó, ứng viên 2 phải đóng nhiều nhất, đến 6 đồng, còn ứng viên 3 đóng ít nhất, 2 đồng.

Sau những ngày chinh chiến với CP, anh Phú về quê nghỉ dưỡng một thời gian và trồng hoa cùng chị. Vườn hoa của anh Phú có kích thước ~m \times n~ và trồng nhiều loại hoa có chiều cao nhất định. Nhưng vì vườn hơi rộng nên chị muốn chọn ra một phần trong vườn có kích thước ~h \times w~ để chăm sóc cho dễ, kịp đón Tết. Để phần vườn đó đẹp nhất, các cây hoa phải có chiều cao bằng nhau và Phú cần phải chọn ra một giá trị chiều cao ~x~ nào đó rồi thực hiện các thao tác: nếu trong phần vườn đang chọn, có hoa cao hơn ~x~ thì Phú sẽ đào đất sâu hơn để trồng cho hoa thấp vừa bằng ~x~; còn nếu hoa thấp hơn ~x~ thì Phú lại đắp đất cao hơn để hoa cao vừa bằng ~x~. Mỗi đơn vị chênh lệch chiều cao sẽ tốn của Phú thời gian không nhỏ, vì thế nên bạn sẽ chọn ra giá trị ~x~ để tiết kiệm công sức nhất có thể.

Biết Phú vất vả nên chị cũng muốn tính toán xem trong các cách chọn vị trí phần vườn thì giá trị ~x~ tương ứng có thể nhỏ nhất là bao nhiêu. Bạn hãy giúp chị trả lời câu hỏi này nhé.

Input

Dòng đầu tiên gồm 4 số nguyên ~m, n, h, w~ cho biết kích thước liên quan, trong đó ~1 \le h \le m \le 10^3~ và ~1 \le w \le n \le 10^3.~

Trong các dòng tiếp theo, ta có thông tin về chiều cao các bông hoa trong vườn chị, giá trị nguyên không âm và không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

5 6 3 3
89 53 45 1 1 76
76 77 66 73 76 53
1 71 91 17 55 61
91 19 9 29 21 89
11 21 81 81 61 81

Sample output

21

Giải thích: ta có thể chỉ ra được nếu chọn phần vườn ~3 \times 3~ ở góc dưới bên trái thì giá trị ~x~ Phú sẽ chọn là ~21~, và chứng minh được số này là nhỏ nhất có thể.

Subtasks

• Có 20% số test có ~m, n ≤ 30~
• Có 20% số test có ~m, n ≤ 100~
• Có 30% số test có ~m, n≤ 300;~
• Có 30% số test có giới hạn như dữ kiện bài ra.