Cho mảng A gồm n số nguyên và q truy vấn có dạng (l,r), tính tổng: A[l]+A[l+1]+…+A[r].

Input

Dòng đầu gồm 2 số nguyên dương n,q.

Dòng thứ hai gồm n số nguyên Ai.Mỗi dòng trong q dòng tiếp theo gồm 2 số nguyên l,r thể hiện một truy vấn.

Output

q dòng mỗi dòng một số nguyên là kết quả cho các truy vấn.

Điều kiện:

    1≤n,q≤10^5.
    1≤Ai≤10^9.

Ví dụ

Input:

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

Output:

1
5
5

Khi chia nguyên liên tục một số nguyên dương N cho 2 chúng ta được một dãy thương và số dư sau đó viết ngược dãy số dư ta được dãy số nhị phân. Dãy số nhị phân đó được gọi là sự biểu diễn của số N trong hệ nhị phân.

Ví dụ: Với số 12 ta có:

N=12        6   3   1   0
Dãy số dư   0   0   1   1

Như vậy số 12 được biểu diễn trong hệ nhị phân là 1100.

Yêu cầu: Tìm số nhị phân tương ứng với số nguyên dương N cho trước.

Dữ liệu vào: Từ tệp văn bản NHIPHAN.INP chỉ ghi số nguyên dương N(N≤10^9)

Kết quả ra: Ghi vào tệp văn bản NHIPHAN.OUT ghi kết quả tìm được.

Ví dụ

NHIPHAN.INP

12

NHIPHAN.OUT

1100

Cho một dãy gồm n số nguyên A1,A2,…,An. Yêu cầu: Hãy tìm chỉ số i sao cho tổng các số từ A1 đến A(i-1) bằng tổng các số từ số từ A(i+1) đến A_n.

Dữ liệu vào: Từ tệp văn bản EQPOINT.INP gồm:

• Dòng đầu tiên gồm một số nguyên dương n.

• Dòng tiếp theo ghi dãy số nguyên dương A1,A2,…,A_n. Mỗi số có giá trị không vượt quá 108.

Kết quả ra: Ghi vào tệp văn bản EQPOINT.OUT chỉ số tìm được. Nếu bài toán vô nghiệm thì ghi số -1.

Ví dụ:

EQPOINT.INP

5
1 3 5 2 2   

EQPOINT.OUT

3

EQPOINT.INP

1
1   

EQPOINT.OUT

1

EQPOINT.INP

4
1 2 3 4 

EQPOINT.OUT

-1

Giới hạn:

Có 50% số test tương ứng với n≤10^3

Có 50% số test tương ứng với n≤10^6

Cho biết X={x1,x2,…,xn} là một hoán vị của {1,2,...,n}. P= 〖{p〗1,p2,...,pn} là dãy nghịch thế của X, trong đó p[i] là số nghịch thế của x[i] (là số phần tử đứng trước xi nhưng có giá trị lớn hơn xi).

Yêu cầu: Cho dãy P. Hãy tìm dãy X.

Dữ liệu vào: Tệp văn bản NGHICTHE2.INP gồm

• Dòng đầu ghi n (n≤1000)

• Dòng tiếp theo ghi p1,p2,...,p_n

Kết quả ra: Tệp văn bản NGHICTHE2.OUT ghi n số x1,x2,...,x_n

Ví dụ

NGHICTHE2.INP

3
0 1 0

NGHICTHE2.OUT

2 1 3

Một nhóm gồm N bạn rủ nhau chụp hình Giáng Sinh. Họ đã tìm được một địa điểm chụp hình dưới chân cầu Rồng-Tp Đà Nẵng, phong cảnh giáng sinh ở đây rất đẹp. Nhóm bạn này muốn ghi lại kỉ niệm mùa đông trong không khí tràn ngập Noel ở đây trong một số bức ảnh để làm kỷ niệm với mong muốn là trong những bức ảnh này phải có mặt tất cả mọi người trong nhóm. Nhưng không may cho họ là tại địa điểm này ai cũng đông đúc và họ ngại nhờ người ngoài nhóm để nhờ họ bấm máy giúp, cho nên mỗi người phải thay nhau chụp ảnh cho các thành viên còn lại của nhóm. Như vậy, để tất cả mọi người đều có mặt trong ảnh, họ phải chụp N tấm ảnh có chung một hậu cảnh. Bức ảnh thứ i (i=1…N) sẽ do người thứ i chụp vì vậy người này sẽ không có mặt trong bức ảnh này.

Trong mỗi bức ảnh, mọi người sẽ đứng theo một hàng ngang và mỗi người sẽ chiếm một diện tích được giới hạn bởi hình chữ nhật bao người đó. Hình chữ nhật giới hạn trong ảnh của người thứ i có chiều ngang là Wi và chiều cao là Hi. Các hình chữ nhật liền kề nhau không chồng lấn lên nhau và cũng không tách rời nhau theo chiều ngang. Diện tích tối thiểu của bức ảnh sẽ là W * H, trong đó W là tổng chiều ngang của tất cả các hình chữ nhật còn H là chiều cao lớn nhất của hình chữ nhật giới hạn của người cao nhất có mặt trong ảnh.

Yêu cầu: Bạn hãy tính diện tích tối thiểu của mỗi bức ảnh trong N bức ảnh đã chụp ở trên. Dữ liệu vào: Tệp văn bản PHOTO.INP gồm:

• Dòng đầu ghi số nguyên N (2≤N≤200000).

• Trong N dòng tiếp theo, với dòng thứ i ghi hai số nguyên Wi và Hi 1≤Wi≤10, 1 ≤ Hi≤1000).

Kết quả ra:

Tệp văn bản PHOTO.OUT ghi N số nguyên trên cùng một dòng, với số thứ i là diện tích tối thiểu của bức ảnh thứ i. Các số cách nhau đúng một dấu cách.

Ví dụ:

PHOTO.INP

3
2 1
1 2
2 1

PHOTO.OUT

6 4 6