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;

int n,a[1000005],b[1000005],newp,root[1000005],m,pos[1000005],lastans;
struct Tree{
	int lc,rc,sum;
}t[10000005];

void doUpdate(int old,int &p,int l,int r,int x){
	p=++newp;
	t[p]=t[old];
	t[p].sum++;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(x<=mid){
		t[p].rc=t[old].rc;
		doUpdate(t[old].lc,t[p].lc,l,mid,x);
	}
	else{
		t[p].lc=t[old].lc;
		doUpdate(t[old].rc,t[p].rc,mid+1,r,x);
	}
}

int doQuery(int k,int L,int R,int l,int r){
	if(l>R||r<L) return 0;
	if(l<=L&&R<=r) return t[k].sum;
	int mid=(L+R)>>1;
	return doQuery(t[k].lc,L,mid,l,r)+doQuery(t[k].rc,mid+1,R,l,r); 
}

int f(int x){
	return (x-1+lastans)%n+1;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[a[i]]=i;
	}
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) doUpdate(root[i-1],root[i],1,n,pos[b[i]]); //可持久化线段树中维护b中的前i个值在a中出现的位置。 
	scanf("%d",&m);
	int x,y,kx,ky;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&x,&y,&kx,&ky);
		x=min(f(x),f(y));
		y=max(f(x),f(y));
		kx=min(f(kx),f(ky));
		ky=max(f(kx),f(ky)); 
		printf("%d\n",lastans=doQuery(root[ky],1,n,x,y)-doQuery(root[kx-1],1,n,x,y)); 
		++lastans;
	}
	return 0;
}