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 tmp[5000000];
void resize(int **arr, int csz) {
  for (int i = 0; i < csz; i++) tmp[i] = (*arr)[i];
  delete[](*arr);
  (*arr) = new int[2 * csz];
  for (int i = 0; i < csz; i++) (*arr)[i] = tmp[i];
}
class SplayTree {
 public:
  int *p, *l, *r, *val, *sz;
  int nNodes, root;
  int SZ;
  void init() {
    nNodes = SZ = 1;
    p = new int[1];
    l = new int[1];
    r = new int[1];
    val = new int[1];
    sz = new int[1];
    p[0] = l[0] = r[0] = 0;
    sz[0] = 0;
    root = 0;
  }
  bool isLeft(int x) { return l[p[x]] == x; }
  void rot(int x) {
    int y = p[x];
    if (p[y] != 0) {
      if (isLeft(y))
        l[p[y]] = x;
      else
        r[p[y]] = x;
    }
    if (isLeft(x)) {
      l[y] = r[x];
      r[x] = y;
      if (l[y] != 0) p[l[y]] = y;
    } else {
      r[y] = l[x];
      l[x] = y;
      if (r[y] != 0) p[r[y]] = y;
    }
    p[x] = p[y];
    p[y] = x;
    sz[x] = sz[y];
    sz[y] = 1 + sz[l[y]] + sz[r[y]];
  }
  void splay(int x) {
    int y = p[x];
    while (y != 0 && p[y] != 0) {
      if (isLeft(y) == isLeft(x))
        rot(x);
      else
        rot(y);
      rot(x);
      y = p[x];
    }
    if (y != 0) rot(x);
    root = x;
  }
  void invinsert(int y, int x) {
    if (val[x] <= val[y]) {
      if (l[y] != 0)
        invinsert(l[y], x);
      else {
        l[y] = x;
        p[x] = y;
      }
    } else {
      if (r[y] != 0)
        invinsert(r[y], x);
      else {
        r[y] = x;
        p[x] = y;
      }
    }
    sz[y] = 1 + sz[l[y]] + sz[r[y]];
  }
  void insert(int v) {
    int x = nNodes++;
    if (nNodes > SZ) {
      resize(&p, SZ), resize(&l, SZ), resize(&r, SZ), resize(&val, SZ),
          resize(&sz, SZ);
      SZ *= 2;
    }
    val[x] = v, l[x] = r[x] = p[x] = 0, sz[x] = 1;
    if (root == 0) {
      root = x;
      return;
    }
    invinsert(root, x);
    splay(x);
  }
  int getRank(int v) {
    int x = root;
    int ans = 0;
    int g = x;
    while (x != 0) {
      g = x;
      if (v >= val[x]) {
        ans += 1 + sz[l[x]];
        x = r[x];
      } else
        x = l[x];
    }
    if (g != 0) splay(g);
    return ans;
  }
};
SplayTree seg[2 * (1 << 20)];
int l[2 * (1 << 20)], r[2 * (1 << 20)];
void init() {
  for (int i = (1 << 20); i < 2 * (1 << 20); i++) {
    l[i] = r[i] = i - (1 << 20);
    seg[i].init();
  }
  for (int i = (1 << 20) - 1; i > 0; i--) {
    l[i] = l[2 * i], r[i] = r[2 * i + 1];
    seg[i].init();
  }
}
void insert(int i, int v) {
  i += (1 << 20);
  for (; i; i /= 2) seg[i].insert(v);
}
int low, high, lowy, highy;
int getNum(int i) {
  if ((l[i] > high) || (r[i] < low)) return 0;
  if ((l[i] <= low) && (r[i] <= high))
    return seg[i].getRank(highy) - seg[i].getRank(lowy - 1);
  return getNum(2 * i) + getNum(2 * i + 1);
}
int N;
int p[1000000], q[1000000];
int qloc[1000000], A[1000000];
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d", &p[i]);
  for (int i = 0; i < N; i++) scanf("%d", &q[i]);
  for (int i = 0; i < N; i++) qloc[q[i] - 1] = i;
  init();
  for (int i = 0; i < N; i++) {
    A[i] = qloc[p[i] - 1];
    insert(i, A[i]);
  }
  int Q;
  int a, b, c, d;
  int x = 0;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    scanf("%d %d %d %d", &a, &b, &c, &d);
    low = min((a - 1 + x) % N, (b - 1 + x) % N);
    high = max((a - 1 + x) % N, (b - 1 + x) % N);
    lowy = min((c - 1 + x) % N, (d - 1 + x) % N);
    highy = max((c - 1 + x) % N, (d - 1 + x) % N);
    x = getNum(1);
    printf("%d\n", x);
    x++;
  }
}
