Cho dãy $A_1, A_2, \ldots, A_N$ độ dài $N$ và số nguyên $M$. Xử lý $Q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $d$ và $k$, và các thao tác sau được thực hiện theo thứ tự:

• Xây dựng dãy mới $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• Với mọi $i$ ($1 \le i \le N$), định nghĩa hậu tố thứ $i$ là $B_i, B_{i+1}, \ldots, B_N$.
• Đưa ra chỉ số của hậu tố nhỏ nhất thứ $k$ theo thứ tự từ điển của dãy $B$.

Dữ liệu vào

Dòng đầu chứa độ dài dãy $N$ và số nguyên $M$.

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$.

Dòng thứ ba chứa số lượng truy vấn $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn $d$ và $k$.

Dữ liệu ra

Với mỗi truy vấn, đưa ra chỉ số của hậu tố nhỏ nhất thứ $k$ theo thứ tự từ điển của dãy $B$, mỗi kết quả trên một dòng.

Ghi chú

Trong truy vấn đầu tiên, dãy $B = [5, 2, 0, 5, 5]$. Sắp xếp tất cả các hậu tố theo thứ tự từ điển thu được $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. Hậu tố nhỏ nhất thứ 4 theo thứ tự từ điển có chỉ số $1$.

Ví dụ

Dữ liệu vào 1

5 6
1 4 2 1 1
3
4 4
2 3
1 1

Dữ liệu ra 1

1
1
5