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;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=1010000;
struct node {
	node *s[2];
	int cnt;
}pool[N*25],*cur=pool,*rt[N];
node* build(int l,int r) {
	node *p=cur++;
	if (l!=r) {
		int md=(l+r)>>1;
		p->s[0]=build(l,md);
		p->s[1]=build(md+1,r);
	}
	return p; 
}
node* modify(node *q,int l,int r,int x) {
	node *p=cur++; *p=*q;
	if (l==r) p->cnt++;
	else {
		int md=(l+r)>>1;
		if (x<=md) p->s[0]=modify(q->s[0],l,md,x);
		else p->s[1]=modify(q->s[1],md+1,r,x);
		p->cnt=p->s[0]->cnt+p->s[1]->cnt;
	}
	return p;
}
int query(node *q,int l,int r,int tl,int tr) {
	if (l==tl&&r==tr) return q->cnt;
	else {
		int md=(l+r)>>1;
		if (tr<=md) return query(q->s[0],l,md,tl,tr);
		else if (tl>md) return query(q->s[1],md+1,r,tl,tr);
		else return query(q->s[0],l,md,tl,md)+query(q->s[1],md+1,r,md+1,tr);
	}
}
int n,x,m,a,b,c,d,ret,p[N],e[N];
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",&x),p[x]=i;
	rep(i,1,n+1) scanf("%d",&x),e[i]=p[x];
	rt[0]=build(1,n);
	rep(i,1,n+1) rt[i]=modify(rt[i-1],1,n,e[i]);
	scanf("%d",&m); ret=-1;
	rep(i,0,m) {
		scanf("%d%d%d%d",&a,&b,&c,&d);
		a=(a+ret)%n+1,b=(b+ret)%n+1,c=(c+ret)%n+1,d=(d+ret)%n+1;
		if (a>b) swap(a,b); if (c>d) swap(c,d);
		ret=query(rt[b],1,n,c,d)-query(rt[a-1],1,n,c,d);
		printf("%d\n",ret);
	}
}
