長さ $N$ の $2$ つの数列 $A_1, A_2, \ldots, A_N$ と $B_1, B_2, \ldots, B_N$ が与えられる。以下のクエリを処理するプログラムを作成せよ。

• i j k: $i \le p, q \le j$ かつ $A_p \times B_q \le k$ を満たす組 $(p, q)$ の個数を出力する。

入力

最初の行に数列の長さ $N$ が与えられる $(1 \le N \le 100{,}000)$。

2 行目に $A_1, A_2, \ldots, A_N$ が与えられる $(1 \le A_i \le 100{,}000)$。

3 行目に $B_1, B_2, \ldots, B_N$ が与えられる $(1 \le B_i \le 100{,}000)$。

4 行目にクエリの個数 $M$ が与えられる $(1 \le M \le 100{,}000)$。

続く $M$ 行のそれぞれにクエリ $i, j, k$ が与えられる $(1 \le i \le j \le N, 1 \le k \le 100{,}000)$。

出力

各クエリについて、答えを 1 行に出力せよ。

入出力例

入力例 1

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

出力例 1

25