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 <cstdio>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <queue>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <complex>
#include <numeric>
#include <map>
#include <time.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<int,ull> piu;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef pair<pii,ll> ppl;
typedef pair<ll,pii> plp;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<double,int> pdi;
typedef pair<int,double> pid;
typedef pair<double,pii> pdp;
typedef pair<double,double> pdd;
typedef pair<pdd,double> pd3;
typedef vector<int> vec;
typedef vector<vec> mat;
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
#define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end())
#define SORTN(x,n) sort((x),(x)+(n))
#define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define COUNT(x,c) count((x).begin(),(x).end(),(c))
#define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
#define REVERSE(x) reverse((x).begin(),(x).end())
#define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
#define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
#define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
#define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
#define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
#define BS(x,a) binary_search((x).begin(),(x).end(),(a))
#define BS2(x,n,a) binary_search((x),(x)+(n),(a))
#define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
#define NP(x) next_permutation((x).begin(),(x).end())
#define MM(x,p) memset((x),(p),sizeof(x))
#define SQ(x) (x)*(x)
#define SC(c1,c2) strcmp(c1,c2)==0
#define mp make_pair
#define INF (1<<30)
#define INFL (1LL<<61)
#define fi first
#define se second
#define MOD 1000000000
#define EPS 1e-8
#define MIN(x,a) x=min(x,a)
#define MAX(x,a) x=max(x,a)
#define madd(x,a) x=(x+a)%MOD
#define msub(x,a) x=(x+MOD-a)%MOD
#define OUTPUT(x) rep(i,x.size())printf("%d%c",x[i],i+1==x.size()?'\n':' ');

int N;
int P[1000000],A,B,C,D,Q;
int tmp[1000000];
const int n=1<<20;
struct Node
{
    int sum,l,r;
}nd[22000000];
int ndptr;
int root[1000001];
void seg_init()
{
    root[0]=0;
    ndptr=n*2-1;
    rep(i,n)nd[i+n-1].l=nd[i+n-1].r=-1;
    for(int i=n-2;i>=0;i--)nd[i].l=i*2+1,nd[i].r=i*2+2;
}
int add(int a,int b,int k,int l,int r)
{
    if(r<=a||b<=l)return k;
    if(a<=l&&r<=b)
    {
        int x=ndptr++;
        nd[x].l=nd[x].r=-1;
        nd[x].sum=1;
        return x;
    }
    int x=ndptr++;
    nd[x].l=add(a,b,nd[k].l,l,(l+r)/2);
    nd[x].r=add(a,b,nd[k].r,(l+r)/2,r);
    nd[x].sum=nd[nd[x].l].sum+nd[nd[x].r].sum;
    return x;
}
int xx;
int f(int a){return (a-1+xx)%N+1;}
int query(int a,int b,int k,int l,int r)
{
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b)return nd[k].sum;
    return query(a,b,nd[k].l,l,(l+r)/2)+query(a,b,nd[k].r,(l+r)/2,r);
}


int main()
{
    scanf("%d",&N);
    rep(i,N)scanf("%d",&P[i]),P[i]--;
    rep(i,N)scanf("%d",&A),tmp[--A]=i;
    rep(i,N)P[i]=tmp[P[i]];
    seg_init();
    rep(i,N)root[i+1]=add(P[i],P[i]+1,root[i],0,n);
    xx=0;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d%d%d%d",&A,&B,&C,&D);
        int l1=min(f(A),f(B));
        int r1=max(f(A),f(B));
        int l2=min(f(C),f(D));
        int r2=max(f(C),f(D));
        l1--,l2--;
        
        int res=query(l2,r2,root[r1],0,n)-query(l2,r2,root[l1],0,n);
        printf("%d\n",res);
        xx=res+1;
    }
}