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, m;
struct node {
  int l, r;
  int leftChild, rightChild;
  int sum;
  node() {}
  node(int _l, int _r, int _leftChild, int _rightChild, int _sum) {
    l = _l;
    r = _r;
    leftChild = _leftChild;
    rightChild = _rightChild;
    sum = _sum;
  }
};
node it[2][1 << 22];
int p[1 << 20];
int q[1 << 20];
int t[2][1 << 20][20];
int tmin[2][1 << 20][20];
void initRMQ() {
  for (int i = 1; i <= n; i++) {
    t[0][i][0] = p[i];
    tmin[0][i][0] = p[i];
  }
  for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      t[0][i][k] = max(t[0][i][k - 1], t[0][i + (1 << (k - 1))][k - 1]);
      tmin[0][i][k] =
          min(tmin[0][i][k - 1], tmin[0][i + (1 << (k - 1))][k - 1]);
    }
  for (int i = 1; i <= n; i++) {
    t[1][i][0] = q[i];
    tmin[1][i][0] = q[i];
  }
  for (int k = 1; (1 << k) <= n; k++)
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      t[1][i][k] = max(t[1][i][k - 1], t[1][i + (1 << (k - 1))][k - 1]);
      tmin[1][i][k] =
          min(tmin[1][i][k - 1], tmin[1][i + (1 << (k - 1))][k - 1]);
    }
}
int f(int z, int x) { return ((z - 1 + x) % n) + 1; }
int RMxQ(int idx, int from, int to) {
  int k = 0;
  while (from + (1 << k) - 1 <= to) k++;
  k--;
  return max(t[idx][from][k], t[idx][to - (1 << k) + 1][k]);
}
int RMnQ(int idx, int from, int to) {
  int k = 0;
  while (from + (1 << k) - 1 <= to) k++;
  k--;
  return min(tmin[idx][from][k], tmin[idx][to - (1 << k) + 1][k]);
}
int nextfree;
int mxx;
void initTree(int idx, int id, int l, int r) {
  if (id == -1) return;
  mxx = max(mxx, id);
  it[idx][id] = node(l, r, -1, -1, 0);
  if (l == r) {
    return;
  }
  it[idx][id].leftChild = id * 2;
  it[idx][id].rightChild = id * 2 + 1;
  initTree(idx, id * 2, l, (l + r) / 2);
  initTree(idx, id * 2 + 1, (l + r) / 2 + 1, r);
  it[idx][id].sum = it[idx][id * 2].sum + it[idx][id * 2 + 1].sum;
}
bool inside(node T, int index) {
  if (index >= T.l && index <= T.r) return true;
  return false;
}
void update(int idx, int id, int l, int r, int upd) {
  if (l == r && l == upd) {
    it[idx][nextfree] = node(l, r, -1, -1, 1);
    nextfree++;
    return;
  }
  if (upd < l || upd > r) return;
  int L = it[idx][id].leftChild;
  int R = it[idx][id].rightChild;
  update(idx, L, l, (l + r) / 2, upd);
  update(idx, R, (l + r) / 2 + 1, r, upd);
  int copy = nextfree;
  if (inside(it[idx][L], upd))
    it[idx][copy] = node(l, r, nextfree - 1, R, 0);
  else if (inside(it[idx][R], upd))
    it[idx][copy] = node(l, r, L, nextfree - 1, 0);
  L = it[idx][copy].leftChild;
  R = it[idx][copy].rightChild;
  it[idx][copy].sum = it[idx][L].sum + it[idx][R].sum;
  nextfree++;
}
int query(int idx, int id, int from, int to) {
  if (from > it[idx][id].r || to < it[idx][id].l) return 0;
  if (it[idx][id].l >= from && it[idx][id].r <= to) return it[idx][id].sum;
  int ret = 0;
  ret += query(idx, it[idx][id].leftChild, from, to);
  ret += query(idx, it[idx][id].rightChild, from, to);
  return ret;
}
vector<int> root[2];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  initTree(0, 1, 1, n);
  initTree(1, 1, 1, n);
  nextfree = mxx + 1;
  root[0].push_back(1);
  root[1].push_back(1);
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    update(0, root[0][i - 1], 1, n, p[i]);
    root[0].push_back(nextfree - 1);
  }
  nextfree = mxx + 1;
  for (int j = 1; j <= n; j++) {
    cin >> q[j];
    update(1, root[1][j - 1], 1, n, q[j]);
    root[1].push_back(nextfree - 1);
  }
  initRMQ();
  cin >> m;
  int A, B, C, D;
  int a, b, c, d;
  int res = -1;
  int mn1, mn2, mx1, mx2, fr, tt;
  for (int i = 0; i < m; i++) {
    cin >> A >> B >> C >> D;
    a = min(f(A, res + 1), f(B, res + 1));
    b = max(f(A, res + 1), f(B, res + 1));
    c = min(f(C, res + 1), f(D, res + 1));
    d = max(f(C, res + 1), f(D, res + 1));
    mn1 = RMnQ(0, a, b);
    mx1 = RMxQ(0, a, b);
    mn2 = RMnQ(1, c, d);
    mx2 = RMxQ(1, c, d);
    fr = max(mn1, mn2);
    tt = min(mx1, mx2);
    cout << mn1 << ' ' << mx1 << ' ' << mn2 << ' ' << mx2 << endl;
    cout << fr << ' ' << tt << endl;
    res = min(query(0, root[0][b], fr, tt) - query(0, root[0][a - 1], fr, tt),
              query(1, root[1][d], fr, tt) - query(1, root[1][c - 1], fr, tt));
    cout << res << endl;
  }
  return 0;
}
