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>
using namespace std;
struct NCS
{
	int lc,rc;
	int sum;
};NCS t[37000000];
int cnt=0,n,q;
struct STree
{
	int rt;
	void bld(int k,int v)
	{
		if(k==0)
		{
			rt=++cnt;
			return ;
		}
		if(t[k].lc==0&&v==0)
		t[k].lc=++cnt;
		if(t[k].rc==0&&v==1)
		t[k].rc=++cnt;
		return ;
	}
	void mdf(int k,int x,int l,int r)
	{
		if(l>x||r<x)
		return ;
		t[k].sum++;
		if(l==r)
		return ;
		int m=(l+r)>>1;
		if(x>m)
		{
			bld(k,1);
			mdf(t[k].rc,x,m+1,r);
			return ;
		}
		bld(k,0);
		mdf(t[k].lc,x,l,m);
		return ;
	}
	int qry(int k,int f,int g,int l,int r)
	{
		if(k==0) return 0;
		if(l>=f&&r<=g)
		return t[k].sum;
		if(l>g||r<f)
		return 0;
		int m=(l+r)>>1;
		return qry(t[k].lc,f,g,l,m)+qry(t[k].rc,f,g,m+1,r);
	}
	void test(int v)
	{
		for(int i=1;i<=v;i++)
		printf("  ");
		return ;
	}
	void chck(int k,int v)
	{
		if(k==0) return ;
		if(k==rt)
		printf("root is=%d\n",rt);
		test(v);printf("K=%d\n",k);
		//test(v);printf("Lq=%d Rq=%d\n",t[k].lq,t[k].rq);
		test(v);printf("Sm=%d\n",t[k].sum);
		test(v);printf("Lson\n"); chck(t[k].lc,v+1);
		test(v);printf("Rson\n"); chck(t[k].rc,v+1);
	}
};
struct WCS
{
	int lq,rq;
	STree s;
};WCS tr[4*1000100];
void bld(int k,int l,int r)
{
	tr[k].lq=l;
	tr[k].rq=r;
	tr[k].s.bld(0,0);
	int m=(l+r)>>1;
	if(l==r) return ; 
	bld(k*2,l,m);
	bld(k*2+1,m+1,r);
	return ;
}
void mdf(int k,int f,int g)
{
	int l=tr[k].lq,r=tr[k].rq;
	if(l>f||r<f) return ;
	//cout<<"l="<<l<<" r="<<r<<" f="<<f<<" g="<<g<<endl;
	//cout<<"Mdf g="<<g<<endl;
	tr[k].s.mdf(tr[k].s.rt,g,1,n);
	if(l==r) return ;
	mdf(k*2,f,g);
	mdf(k*2+1,f,g);
	return ;
}
int qry(int k,int f,int g,int v,int w)
{
	int l=tr[k].lq,r=tr[k].rq;
	if(l>g||r<f) return 0;
	if(l>=f&&r<=g)
	{
		//int gt=tr[k].s.qry(tr[k].s.rt,v,w);
		//cout<<"v="<<v<<" w="<<w<<" get="<<gt<<endl;
		return tr[k].s.qry(tr[k].s.rt,v,w,1,n);
	}
	return qry(k*2+1,f,g,v,w)+qry(k*2,f,g,v,w);
}
int a[1010240],b[1010240],f[1010240],g[1010240],ans=1;
int fc(int z)
{
	return ((z-ans)%n+n)%n+1;
}
int mn(int z,int w)
{
	if(z<w)
	return z;
	return w;
}
int mx(int z,int w)
{
	if(z>w)
	return z;
	return w;
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d",&n);
	bld(1,1,n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		g[b[i]]=i;
	}
	//cout<<"Test"<<endl;
	for(int i=1;i<=n;i++)
	{
		//Modify num"i" x=a[i],y=b[i]
		mdf(1,f[i],g[i]);
		//cout<<"Build: "<<f[i]<<" "<<g[i]<<endl;
		//if(i%10000==0)
		//cout<<"N="<<cnt<<endl;
	}
	//cout<<"Rest"<<endl;
/*
7
1 6 3 7 4 5 2
7 2 5 4 6 1 3
1000
1 4 3 7
*/
	scanf("%d",&q);
	while(q--)
	{
		int q,w,e,r;
		scanf("%d%d%d%d",&q,&w,&e,&r);
		//q=mn(fc(q),fc(w));
		//w=mx(fc(q),fc(w));
		//e=mn(fc(e),fc(r));
		//r=mx(fc(e),fc(r));
		//cout<<q<<" "<<w<<" "<<e<<" "<<r<<endl;
		ans=qry(1,q,w,e,r);
		printf("%d\n",ans);
	}
	return 0;
}