Deux séquences de longueur $N$, $A_1, A_2, \ldots, A_N$ et $B_1, B_2, \ldots, B_N$, sont données. Écrire un programme pour traiter les requêtes suivantes :

• i j k : afficher le nombre de paires $(p, q)$ telles que $i \le p, q \le j$ et $A_p \times B_q \le k$.

Entrée

La première ligne donne la longueur $N$ des séquences $(1 \le N \le 100{,}000)$.

La deuxième ligne donne $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100{,}000)$.

La troisième ligne donne $B_1, B_2, \ldots, B_N$ $(1 \le B_i \le 100{,}000)$.

La quatrième ligne donne le nombre de requêtes $M$ $(1 \le M \le 100{,}000)$.

Les $M$ lignes suivantes donnent chacune une requête $i, j, k$ $(1 \le i \le j \le N, 1 \le k \le 100{,}000)$.

Sortie

Pour chaque requête, afficher la réponse sur une seule ligne.

Exemples

Entrée 1

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

Sortie 1

25