Little H 有两个长度均为 $n$ 的排列 $a$ 和 $b$。 共有 $q$ 次询问，每次询问给定 $a$ 的一个区间 $[l, r]$ 和 $b$ 的一个区间 $[L, R]$。他想知道 $\sum_{i=l}^{r} \sum_{j=L}^{R} \gcd^2(a_i, b_j)$ 的值，你只需要输出结果对 $2^{32}$ 取模后的值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示 $a$ 和 $b$ 的长度。 第二行包含 $n$ 个整数，表示排列 $a$ ($1 \le a_i \le n$)，保证当 $i \neq j$ 时 $a_i \neq a_j$。 第三行包含 $n$ 个整数，表示排列 $b$ ($1 \le b_i \le n$)，保证当 $i \neq j$ 时 $b_i \neq b_j$。 第四行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示询问次数。 接下来 $q$ 行，每行包含四个整数 $l, r, L, R$ ($1 \le l \le r \le n, 1 \le L \le R \le n$)，表示第 $i$ 次询问的区间。

输出格式

输出 $q$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次询问的答案。

样例

样例输入 1

5
4 1 5 3 2
1 2 3 4 5
5
3 3 2 3
3 4 2 4
3 4 3 4
5 5 1 1
1 1 2 2

样例输出 1

2
14
12
1
4