ARGUMENT - Cãi Nhau
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: ami

          Hôm nay Ami mới cãi nhau với crush. Cậu buồn quá không có tâm trạng viết đề nên cậu sẽ vào vấn đề luôn. Ami có một dãy số gồm n phần tử. Ami cần các bạn trả lời các câu hỏi. Mỗi câu hỏi gồm 2 số u và k, các bạn cần tình toán giúp Ami tổng của k phần tử nhỏ nhất trong tiền tố độ dài u của dãy số.

Dữ liệu vào

Dòng đầu tiên gồm 2 số nguyên dương n (n <= 105) là số phần tử của dãy số và q (q <= 105) là số câu hỏi Ami cần các bạn trả lời.

Tiếp theo là n số nguyên dương a1,a2,..,an (ai <= 106) là các phần tử của dãy.

Q dòng cuối cùng, mỗi dòng chứa 2 số nguyên dương u và k (k <= u <= n) là một câu hỏi của Ami.

Dữ liệu ra

Một dòng gồm q số - kết quả của câu hỏi tương ứng.

Ví dụ

Input

5 3

1 2 3 4 5

1 1

2 2

3 3

Output

1 3 6

Giải thích

Vì k trùng u nên kết quả là tổng các số trong tiền tố độ dài u tương ứng.Ví dụ

Back to Top