Siêu thị SHOPPRO là một trong các siêu thị lớn ở đất nước XYZ. Trong siêu thị có ~n~ gian hàng được đánh số từ ~1~ đến ~n~. Một món hàng ở gian hàng thứ ~i~ có giá ~a_i~, và có thể xem số lượng hàng ở mỗi gian hàng là vô hạn.

Trong ngày hôm nay, siêu thị chào đón ~q~ vị khách. Vị khách thứ ~i~ mang theo số tiền là ~x_i~, và sẽ lần lượt ghé thăm các gian hàng từ ~p_i~ đến ~n~. Mỗi khi ghé thăm một gian hàng, nếu số tiền còn lại đủ để mua một món hàng từ gian hàng đó, thì vị khách sẽ chi tiền ra mua một món hàng từ gian hàng.

Yêu cầu: Hãy cho biết mỗi vị khách mua được bao nhiêu món hàng.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n,q~ ~(n,q \le 10^5)~ - số gian hàng và số vị khách.

• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 100)~ - giá một món hàng tại các gian hàng.

• ~q~ dòng tiếp theo:

  • Dòng thứ ~i~ gồm hai số nguyên dương ~x_i,p_i~ ~(x_i \le 10^7,p_i \le n)~ - số tiền vị khách thứ ~i~ mang theo và gian hàng đầu tiên mà vị khách thứ ~i~ viếng thăm.

Output

Ghi ra ~q~ dòng, dòng thứ ~i~ cho biết số món hàng mà vị khách thứ ~i~ mua được.

Scoring

Sample Input 1

7 4
9 3 5 2 6 3 2
11 3
11 1
100 2
1 1

Sample Output 1

3
2
6
0

Notes

Vị khách thứ nhất sẽ mua hàng ở gian hàng ~3~, ~4~ và ~6~. Việc mua hàng của vị khách thứ nhất diễn ra theo bảng sau:

Vị khách thứ hai sẽ mua hàng ở gian hàng ~1~ và ~4~.

Vị khách thứ ba sẽ mua hàng ở tất cả các gian hàng từ ~2~ đến ~7~.

Vị khách thứ tư không có đủ tiền để mua hàng ở bất kỳ gian hàng nào.