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 <climits>
#include <cstdlib>
#include <cstring>
#define ROOT root,l,r
#define LSON tree[root].lson,l,mid
#define RSON tree[root].rson,mid+1,r
using namespace std;
const int maxn=3*1e7+5;
struct seg
{
	int size;
	int lson;
	int rson;
}tree[maxn];
struct node
{
	int data,id;
}a[1000005],b[1000005];
int n,q,c[1000005],last;
bool comp(node i,node j)
{
	return i.data<j.data;
}
int h[1000005],sz,l1,l2,r1,r2;
int a1,b1,c1,d1;
int F(int x,int last)
{
	return (x-1+last)%n+1;
}
int build(int l, int r)//空树，建立树的形态 
{
    int p=++sz;
    tree[p].size=0;
    if(l!=r){
        int mid=(l+r)>>1;
        tree[p].lson=build(l,mid);
        tree[p].rson=build(mid+1,r);
    }
    return p;
}
int update(int p,int x)
{
	sz++; int now=sz; int tmp=now; tree[now].size=tree[p].size+1;
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(x>mid)
		{
			tree[now].rson=++sz; tree[now].lson=tree[p].lson; now=sz; l=mid+1;
			p=tree[p].rson;
		}
		else
		{
			tree[now].lson=++sz; tree[now].rson=tree[p].rson; now=sz; r=mid;
			p=tree[p].lson;
		}
		
		tree[now].size=tree[p].size+1;
	}
	return tmp;
}
int query(int root,int l,int r,int L,int R)
{
	if(L<=l && R>=r)
	{
		return tree[root].size;
	}
	else
	{
		int mid=(l+r)>>1;
		int ans=0;
		if(L>mid) ans=query(RSON,L,R);
		else if(R<=mid) ans=query(LSON,L,R);
		else ans=query(LSON,L,R)+query(RSON,L,R);
		return ans;	
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].data); a[i].id=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i].data); b[i].id=i;
	}
	sort(a+1,a+n+1,comp); sort(b+1,b+n+1,comp);
	for(int i=1;i<=n;i++)
		c[b[i].id]=a[i].id;
	h[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		h[i]=update(h[i-1],c[i]);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d%d",&a1,&b1,&c1,&d1);
		l1=min(F(a1,last),F(b1,last));r1=max(F(a1,last),F(b1,last));
		l2=min(F(c1,last),F(d1,last));r2=max(F(c1,last),F(d1,last));
		last=(query(h[r1],1,n,l2,r2)-query(h[l1-1],1,n,l2,r2));
	//	cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<endl;
		printf("%d\n",last); last++;
	}
	return 0;
}