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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define Wild_Donkey 0
using namespace std;
inline unsigned RD() {
  unsigned intmp(0);
  char rdch(getchar());
  while (rdch < '0' || rdch > '9') rdch = getchar();
  while (rdch >= '0' && rdch <= '9') {
    intmp = (intmp << 3) + (intmp << 1) + rdch - '0';
    rdch = getchar();
  }
  return intmp;
}
inline int RDsg() {
  int rdtp(0), rdsg(1);
  char rdch(getchar());
  while ((rdch < '0' || rdch > '9') && (rdch != '-')) rdch = getchar();
  if (rdch == '-') {
    rdsg = -1;
    rdch = getchar();
  }
  while (rdch >= '0' && rdch <= '9') {
    rdtp = (rdtp << 3) + (rdtp << 1) + rdch - '0';
    rdch = getchar();
  }
  return rdtp * rdsg;
}
unsigned a[1000005],b[1000005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
struct Node {
  Node *LS, *RS;
  unsigned Val;
}N[20000005], *Order[1000005], *CntN(N);
void Add(Node *x, Node *y, unsigned L, unsigned R) {
//  printf("[%u, %u] %u %u\n", L, R, x - N, y - N);
  if(!x) {
    y->Val = 1;
    if (L == R) return;
    register unsigned Mid((L + R) >> 1);
    if(A <= Mid) {
      Add(NULL, y->LS = ++CntN, L, Mid);
    } else {
      Add(NULL, y->RS = ++CntN, Mid + 1, R);
    }
    return;
  }
  y->Val = x->Val + 1;
  if(L == R) return;
  register unsigned Mid((L + R) >> 1);
  if(Mid >= A) {
    y->RS = x->RS;
    Add(x->LS, y->LS = ++CntN, L, Mid);
  } else {
    y->LS = x->LS;
    Add(x->RS, y->RS = ++CntN, Mid + 1, R);
  }
}
void Qry(Node *x, unsigned L, unsigned R){
//  printf("[%u, %u] Sons: [%u, %u] Qry %u Val %u\n", L, R, x->LS - N, x->RS - N, x - N, x->Val);
  if((A <= L) && (R <= B)) {Tmp += x->Val; return;}
  register unsigned Mid((L + R) >> 1);
  if ((A <= Mid) && (x->LS)) Qry(x->LS, L, Mid);
  if ((Mid < B) && (x->RS)) Qry(x->RS, Mid + 1, R); 
}
inline unsigned F(unsigned x) {
  return ((x - 1 + Ans) % n) + 1;
}
int main() {
  n = RD();
  for (register unsigned i(1); i <= n; ++i) {
    a[RD()] = i;
  }
  for (register unsigned i(1); i <= n; ++i) {
    b[a[RD()]] = i;
  }
  Order[0] = N;
  for (register unsigned i(1); i <= n; ++i) {
    A = b[i], Add(Order[i - 1], Order[i] = ++CntN, 1, n);       
  }
  m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    C = F(RD()), D = F(RD()), A = F(RD()), B = F(RD());
    if(C > D) swap(C, D); 
    if(A > B) swap(A, B);
    if(n == 1000000)printf("%u: %u %u %u %u\n", i, C, D, A, B);
    Tmp = 0, Qry(Order[D], 1, n);
    Ans = Tmp, Tmp = 0, Qry(Order[C - 1], 1, n);
    printf("%u\n", Ans = Ans - Tmp);
    ++Ans;
  }
//  }
  return Wild_Donkey;
}