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<algorithm>
#include<map>
using namespace std;
int tp=1,ans=1,n,q;
struct Node
{
	int lc,rc;
	int lq,rq;
	int sum;
};Node t[23*1010240];
void bld(int k,int l,int r)
{
	//cout<<k<<" "<<l<<" "<<r<<endl;
	t[k].lq=l; t[k].rq=r;
	if(l==r) return ;
	int m=(l+r)>>1;
	t[k].lc=(++tp);
	bld(tp,l,m);
	t[k].rc=(++tp);
	bld(tp,m+1,r);
	return ;
}
void mdf(int k,int g,int x)
{
	t[k]=t[g];
	int l=t[k].lq,r=t[k].rq,m=(l+r)>>1;
	t[k].sum++;	
	if(l==r)
	return ;
	if(x<=m)
	{
		t[k].lc=(++tp);
		mdf(tp,t[g].lc,x);
	}
	if(x>m)
	{
		t[k].rc=(++tp);
		mdf(tp,t[g].rc,x);
	}
	return ;
}
int qry(int f,int g,int v,int w)
{
	int l=t[f].lq,r=t[f].rq;
	if(l>=v&&r<=w)
	return t[g].sum-t[f].sum;
	if(l>w||r<v) return 0;
	return qry(t[f].lc,t[g].lc,v,w)+qry(t[f].rc,t[g].rc,v,w);
}
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 a[1501024],f[1501024],xc,rt[1501024];
int main()
{
	scanf("%d",&n);
	bld(1,1,n); rt[0]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&xc);
		rt[i]=++tp;
		mdf(tp,rt[i-1],f[xc]);
	}
	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(rt[e-1],rt[r],q,w);
		printf("%d\n",ans);
	}
	return 0;
}