You are given two permutations p and q, consisting of n elements, and m queries of the form: l1, r1, l2, r2 (l1 ≤ r1; l2 ≤ r2). 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 [l1, r1] (borders included), and position in the second permutation is in segment [l2, r2] (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 g1, g2, ..., gn is such number i, that gi = v.

Input

The first line contains one integer n (1 ≤ n ≤ 106), the number of elements in both permutations. The following line contains n integers, separated with spaces: p1, p2, ..., pn (1 ≤ pi ≤ n). These are elements of the first permutation. The next line contains the second permutation q1, q2, ..., qn in same format.

The following line contains an integer m (1 ≤ m ≤ 2·105), 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 l1, r1, l2, r2 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 l1 = min(f(a), f(b)), r1 = max(f(a), f(b)), l2 = min(f(c), f(d)), r2 = max(f(c), f(d)). 

Output

Print a response for each query in a separate line.

Examples

Input

3
3 1 2
3 2 1
1
1 2 3 3


Output

1


Input

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


Output

1
1
2
1
1
1
1
1 1 1 1

1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define gc getchar()
#define mid (l + r >> 1)
#define N 2000005
#define M 40000005
using namespace std;
int ln[M],rn[M],sum[M],root[N];
int n,a[N],pos[N],q,ans,cnt;
int read()
{
    int x = 1;
    char ch;
    while (ch = gc,ch < '0' || ch > '9') 
		if (ch == '-') 
			x = -1;
    int s = ch-'0';
    while (ch = gc,ch >= '0' && ch <= '9') 
		s = s * 10 + ch - '0';
    return s * x;
}
void ins(int cur,int l,int r,int x,int last)
{
    cur = ++cnt;
    ln[cur] = ln[last];
    rn[cur] = rn[last];
    sum[cur] = sum[last] + 1;
    if (l == r) 
		return;
    if (x <= mid) 
		ins(ln[cur],l,mid,x,ln[last]);
    else ins(rn[cur],mid + 1,r,x,rn[last]);
}
int qry(int &cur,int l,int r,int L,int R)
{
    if (L <= l && R >= r) 
		return sum[cur];
    int ret = 0;
    if (L <= mid) 
		ret += qry(ln[cur],l,mid,L,R);
    if (R > mid) 
		ret += qry(rn[cur],mid + 1,r,L,R);
    return ret;
}
int f(int x)
{
    return (x - 1 + ans) % n + 1;
}
int main()
{
    n = read();
    for(int i = 1;i <= n;i++) 
		pos[read()] = i;
    for(int i = 1;i <= n;i++) 
		a[i] = pos[read()];
    for(int i = 1;i <= n;i++) 
		ins(root[i],1,n,a[i],root[i - 1]);
    q = read();
    while(q--)
    {
        int x = f(read()),y = f(read()),z = f(read()),w = f(read());
        if (x > y) 
			swap(x,y);
        if (z > w) 
			swap(z,w);
        printf("%d\n",ans = qry(root[w],1,n,x,y) - qry(root[z - 1],1,n,x,y));
        ans++;
    }
    return 0;
}
