Sequence and Queries 9

Two sequences of length $N$ are given: $A_1, A_2, \dots, A_N$ and $B_1, B_2, \dots, B_N$. Write a program that processes the following query.

• i j k: print the number of pairs $(p, q)$ such that $i \le p \le j$, $i \le q \le j$, and $A_p \times B_q \le k$.

The indices $p$ and $q$ are chosen independently, so a pair with $p = q$ also counts.

The first line contains the size of the sequences, $N$ ($1 \le N \le 100000$).

The second line contains $A_1, A_2, \dots, A_N$. ($1 \le A_i \le 100000$)

The third line contains $B_1, B_2, \dots, B_N$. ($1 \le B_i \le 100000$)

The fourth line contains the number of queries, $M$ ($1 \le M \le 100000$).

Each of the next $M$ lines contains one query $i$, $j$, $k$. ($1 \le i \le j \le N$, $1 \le k \le 100000$)

For each query, print the answer on its own line, in the order the queries are given.