Các bãi biển mùa hè luôn đông du khách. Để tiện quản lý, bờ biển được chia thành ~k~ lô liên tiếp, đánh số từ ~1~ đến ~k~. Công ty dịch vụ có ~n~ xe lưu động chuyên phục vụ nước giải khát. Mỗi khi có khách gọi đến Trung tâm quản lý, một xe sẽ được điều độ tới lô đó.

Ban đầu, xe thứ ~i~ đang đỗ tại lô ~p_i~. Thời gian di chuyển từ lô ~u~ tới lô ~v~ là ~|u-v|~. Khi xe hoàn thành một yêu cầu ở lô nào đó, nếu nhận nhiệm vụ tiếp theo thì xe xuất phát từ chính lô đang dừng. Việc phục vụ tại lô được coi là hoàn thành ngay khi xe tới nơi.

Trong ngày có tổng cộng ~m~ yêu cầu. Yêu cầu thứ ~j~ được gửi từ lô ~x_j~ tại thời điểm ~t_j~. Khi một yêu cầu tới, nó lập tức được chuyển cho xe sao cho thời gian chờ đợi của yêu cầu đó là nhỏ nhất (thời gian chờ là khoảng thời gian từ ~t_j~ đến lúc xe được chỉ định tới lô ~x_j~).

• Nếu có nhiều yêu cầu đến cùng một thời điểm, chúng được xử lý theo đúng thứ tự xuất hiện trong biên bản (tức theo thứ tự ~j~ tăng dần trong input).
• Nếu có nhiều xe cho cùng thời gian chờ nhỏ nhất, chọn xe có số thứ tự nhỏ nhất.
• Mỗi xe thực hiện các yêu cầu theo đúng thứ tự mà nó đã nhận; chỉ khi hoàn thành xong yêu cầu trước thì mới bắt đầu di chuyển cho yêu cầu tiếp theo của chính xe đó.

Yêu cầu

Với mỗi yêu cầu ~j~, hãy xác định chỉ số xe được Trung tâm chỉ định để phục vụ yêu cầu đó.

Dữ liệu

• Dòng 1 chứa hai số nguyên ~n~ và ~k~ (~1 \le n, k \le 10^5~).
• Dòng 2 chứa ~n~ số nguyên ~p_1, p_2, \dots, p_n~ (~1 \le p_i \le k~).
• Dòng 3 chứa số nguyên ~m~ (~1 \le m \le 10^5~).
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~t_j~ và ~x_j~ (~0 \le t_j \le 10^5~, ~1 \le x_j \le k~).

Kết quả

In ra ~m~ dòng, mỗi dòng là một số nguyên — chỉ số xe phục vụ yêu cầu tương ứng.

Ví dụ

Ví dụ 1

Input

3 10
1 5 10
5
1 7
2 4
5 10
6 1
7 7

Output

2
1
3
1
2

Giải thích

Ví dụ 1

• Yêu cầu 1 tại ~t=1~, ~x=7~: xe 2 từ lô ~5~ tới nhanh nhất.
• Yêu cầu 2 tại ~t=2~, ~x=4~: xe 1 từ lô ~1~ tới nhanh nhất.
• Yêu cầu 3 tại ~t=5~, ~x=10~: xe 3 đang ở ~10~ nên được chọn.
• Yêu cầu 4 tại ~t=6~, ~x=1~: xe 1 đã sẵn ở ~4~ và tới ~1~ nhanh nhất.
• Yêu cầu 5 tại ~t=7~, ~x=7~: xe 2 được chọn theo tiêu chí thời gian chờ nhỏ nhất.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, k \le 10^5~
• ~1 \le m \le 10^5~
• ~1 \le p_i \le k~
• ~0 \le t_j \le 10^5~
• ~1 \le x_j \le k~