Cho dãy ~a~ gồm ~n~ số nguyên.

Bạn phải trả lời ~q~ truy vấn. Mỗi truy vấn cho hai số nguyên ~b, c~, bạn cần tìm số cặp ~(i, j)~ thỏa mãn:

• ~1 \le i < j \le n~.
• ~a_i + a_j = b~.
• ~a_i \times a_j = c~.

Đầu vào

• Dòng thứ nhất chứa một số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le |a_i| \le 10^9~).
• Dòng thứ ba chứa một số nguyên dương ~q~ (~1 \le q \le 2 \times 10^5~).
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~b, c~ mô tả một truy vấn (~1 \le |b| \le 2 \times 10^9~; ~1 \le |c| \le 10^{18}~).

Đầu ra

Với mỗi truy vấn theo đúng thứ tự trong đầu vào, in ra một dòng một số nguyên duy nhất là số cặp ~(i, j)~ thỏa mãn các điều kiện trên.

Giới hạn

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10^3~, ~q = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~|a_i| \le 10^6~, ~|c| \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~|c| \le 10^9~.
• Subtask ~4~ (~20\%~ số điểm): Các phần tử ~a_i~ phân biệt từng đôi một.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

3
1 3 2
1
3 2

Đầu ra

1