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 <= 10⁵) là số phần tử của dãy số và q (q <= 10⁵) 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 a₁,a₂,..,a_n (a_i <= 10⁶) 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.