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 \(k\:r\), 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\%\) 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\).