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<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int maxtot=2e7+10;
int n,q;
int p1[maxn],p2[maxn],pos[maxn],a[maxn];
int root[maxn];
int l1,r1,l2,r2;
int tot=0;
struct node
{
    int lc,rc,cnt;
}b[maxtot];
void pushup(int p)
{
    b[p].cnt=b[b[p].lc].cnt+b[b[p].rc].cnt;
}
int update(int pre,int l,int r,int pos,int val)
{
    int cur=++tot;
    b[cur]=b[pre];
    if (l==r) {
        b[cur].cnt+=val;
        return cur;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) b[cur].lc=update(b[pre].lc,l,mid,pos,val);
    else b[cur].rc=update(b[cur].rc,mid+1,r,pos,val);
    pushup(cur);
    return cur;
}
int querySum(int p,int l,int r,int L,int R)
{
    if (L>R) return 0;
    if (L<=l&&r<=R) return b[p].cnt;
    int mid=(l+r)>>1;
    int ans=0;
    if (L<=mid) ans+=querySum(b[p].lc,l,mid,L,R);
    if (R>mid) ans+=querySum(b[p].rc,mid+1,r,L,R);
    return ans;
}
int f(int z,int x)
{
    return (z-1+x)%n+1;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&p1[i]);
    for (int i=1;i<=n;i++) scanf("%d",&p2[i]);
    for (int i=1;i<=n;i++) pos[p2[i]]=i;
    for (int i=1;i<=n;i++) a[i]=pos[p1[i]];
    root[0]=0;
    for (int i=1;i<=n;i++) root[i]=update(root[i-1],1,n,a[i],1);
    scanf("%d",&q);
    int lastans=0;
    while (q--) {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int l_1=f(l1,lastans),r_1=f(l2,lastans);
        int l_2=f(l2,lastans),r_2=f(r2,lastans);
        l1=min(l_1,r_1); r1=max(l_1,r_1);
        l2=min(l_2,r_2); r2=max(l_2,r_2);
        printf("%d\n",querySum(root[r1],1,n,l2,r2)-querySum(root[l1-1],1,n,l2,r2));
    }
    return 0;
}
