Cho dãy số có $n$ phần tử, bắt đầu từ chỉ số $1$ và số $m$ nguyên dương. Với mỗi truy vấn dạng $kr$, tìm chỉ số của số thứ $k$ trong dãy chia $m$ dư $r$.

Đầu vào

Dòng đầu tiên chứa số tự nhiên $n,m$ và $q$ $(1\le n,q\le {10}^6,1\le m\le 100)$ lần lượt là số phần tử của dãy, số chia và số lần truy vấn.

Dòng tiếp theo chứa $n$ nguyên (giá trị tuyệt đối không quá ${10}^9$) là các phần tử của dãy số.

$q$ dòng tiếp theo mỗi dòng chứa hai số nguyên $k,r$ $(1\le k\le n,0\le r\le m)$ biểu diễn một truy vấn.

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Đầu ra

Với mỗi truy vấn, in ra trong một dòng chỉ số của số cần tìm.

Nếu số cần tìm không tồn tại, xuất ra $-1$.

Subtask

$30\mathrm{\%}$ số test có $n,q\le 1000$.

Ví dụ

Đầu vào:

9 3 4
2 -2 5 8 3 9 6 7 0
1 1
2 1
2 0
10 0

Đầu ra:

2
8
6
-1

Giải thích:

• Số thứ nhất chia $3$ dư $1$ có chỉ số $2$.
• Số thứ hai chia $3$ dư $1$ có chỉ số $8$.
• Số thứ hai chia $3$ dư $0$ có chỉ số $6$
• Không có số thứ $10$ chia $3$ dư $0$, xuất ra $-1$.