Cho hai dãy độ dài $N$, $A_1, A_2, \ldots, A_N$ và $B_1, B_2, \ldots, B_N$. Viết chương trình xử lý các truy vấn sau:

• i j k: đưa ra số lượng cặp $(p, q)$ thỏa mãn $i \le p, q \le j$ và $A_p \times B_q \le k$.

Dữ liệu vào

Dòng đầu tiên cho độ dài $N$ của các dãy $(1 \le N \le 100{,}000)$.

Dòng thứ hai cho $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100{,}000)$.

Dòng thứ ba cho $B_1, B_2, \ldots, B_N$ $(1 \le B_i \le 100{,}000)$.

Dòng thứ tư cho số lượng truy vấn $M$ $(1 \le M \le 100{,}000)$.

$M$ dòng tiếp theo, mỗi dòng cho một truy vấn $i, j, k$ $(1 \le i \le j \le N, 1 \le k \le 100{,}000)$.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng.

Ví dụ

Dữ liệu vào 1

5
1 1 1 1 1
1 1 1 1 1
1
1 5 1

Dữ liệu ra 1

25