J. Sum of Squares of GCDs
time limit per test
4 с
memory limit per test
1024 МБ
input
standard input
output
standard output

Little H has two permutations $$$a$$$ and $$$b$$$, both of length $$$n$$$.

There are $$$q$$$ queries, and for each query, he will give you an interval $$$[l,r]$$$ for $$$a$$$ and an interval $$$[L, R]$$$ for $$$b$$$. He wants to know the value of $$$\sum\limits_{i=l}^r \sum\limits_{j=L}^R \gcd^2(a_i,b_j)$$$, but you only need to provide the result modulo $$$2^{32}$$$.

Input

The first line contains a number $$$n$$$ $$$(1\leq n \leq 10^5)$$$, representing the length of $$$a$$$ and $$$b$$$.

The next line contains $$$n$$$ integers, representing the permutation $$$a$$$ $$$(1 \leq a_i \leq n)$$$, ensuring that $$$a_i \neq a_j$$$ for $$$i \neq j$$$.

The following line contains $$$n$$$ integers, representing the permutation $$$b$$$ $$$(1 \leq b_i \leq n)$$$, ensuring that $$$b_i \neq b_j$$$ for $$$i \neq j$$$.

The next line contains a number $$$q$$$ $$$(1\leq q \leq 10^5)$$$, representing the number of queries.

The next $$$q$$$ lines each contain four numbers $$$l,r,L,R$$$ $$$(1 \leq l \leq r \leq n, 1 \leq L \leq R \leq n)$$$, representing the intervals for the $$$i$$$-th query.

Output

Output $$$q$$$ lines, where the $$$i$$$-th line outputs an integer representing the answer to the $$$i$$$-th query.

Example
Input
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
Output
2
14
12
1
4