You are given two permutations $*p*$ and $*q*$, consisting of $*n*$ elements, and $*m*$ queries of the form: $*l*_{1}, *r*_{1}, *l*_{2}, *r*_{2}$ $(*l*_{1} ≤ *r*_{1}; *l*_{2} ≤ *r*_{2})$. The response for the query is the number of such integers from $1$ to $*n*$, that their position in the first permutation is in segment $[*l*_{1}, *r*_{1}]$ (borders included), and position in the second permutation is in segment $[*l*_{2}, *r*_{2}]$ (borders included too).

A permutation of $*n*$ elements is the sequence of $*n*$ distinct integers, each not less than $1$ and not greater than $*n*$.

Position of number $*v*$ $(1 ≤ *v* ≤ *n*)$ in permutation $*g*_{1}, *g*_{2}, ..., *g*_{*n*}$ is such number $*i*$, that $*g*_{*i*} = *v*$.

Input

The first line contains one integer $*n* (1 ≤ *n* ≤ 10^{6})$, the number of elements in both permutations. The following line contains $*n*$ integers, separated with spaces: $*p*_{1}, *p*_{2}, ..., *p*_{*n*} (1 ≤ *p*_{*i*} ≤ *n*)$. These are elements of the first permutation. The next line contains the second permutation $*q*_{1}, *q*_{2}, ..., *q*_{*n*}$ in same format.

The following line contains an integer $*m* (1 ≤ *m* ≤ 2·10^{5})$, that is the number of queries.

The following $*m*$ lines contain descriptions of queries one in a line. The description of the $*i*$-th query consists of four integers: $*a*, *b*, *c*, *d* (1 ≤ *a*, *b*, *c*, *d* ≤ *n*)$. Query parameters $*l*_{1}, *r*_{1}, *l*_{2}, *r*_{2}$ are obtained from the numbers $*a*, *b*, *c*, *d*$ using the following algorithm:

1. Introduce variable $*x*$. If it is the first query, then the variable equals $0$, else it equals the response for the previous query plus one.
2. Introduce function $*f*(*z*) = ((*z* - 1 + *x*) *mod* *n*) + 1$.
3. Suppose $*l*_{1} = *min*(*f*(*a*), *f*(*b*)), *r*_{1} = *max*(*f*(*a*), *f*(*b*)), *l*_{2} = *min*(*f*(*c*), *f*(*d*)), *r*_{2} = *max*(*f*(*c*), *f*(*d*))$.

Output

Print a response for each query in a separate line.