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