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>
class fastin {
 private:
  int _ch, _f;

 public:
  inline fastin& operator>>(char& c) {
    c = getchar();
    return *this;
  }
  template <typename _Tp>
  inline fastin& operator>>(_Tp& _x) {
    _x = 0;
    while (!isdigit(_ch)) _f |= (_ch == 45), _ch = getchar();
    while (isdigit(_ch))
      _x = (_x << 1) + (_x << 3) + (_ch ^ 48), _ch = getchar();
    _f && (_x = -_x, _f = 0);
    return *this;
  }
  fastin() { _ch = _f = 0; }
} fin;
class fastout {
 private:
  int _val[32], _head;

 public:
  inline fastout& operator<<(char c) {
    putchar(c);
    return *this;
  }
  template <typename _Tp>
  inline fastout& operator<<(_Tp _x) {
    _Tp _k;
    if (_x == 0) {
      putchar('0');
      return *this;
    }
    if (_x < 0) putchar('-'), _x = -_x;
    while (_x > 0)
      _k = _x / 10, ++_head, _val[_head] = (_x - (_k << 1) - (_k << 3)) ^ 48,
      _x = _k;
    while (_head > 0) putchar(_val[_head]), --_head;
    return *this;
  }
  fastout() { _head = 0; }
} fout;
const int maxn = 1000004;
const int mod = 998244353, inf = 1e9 + 7;
int val[maxn];
class chairman_tree {
 private:
  int root[maxn], cntnode;
  struct NODE {
    int ls, rs, sum;
  } t[maxn * 40];
  int ql, qr;
  void update(int& p, int l, int r, int x) {
    t[++cntnode] = t[p], p = cntnode, ++t[p].sum;
    if (l == r) return;
    if (x <= ((l + r) >> 1))
      update(t[p].ls, l, ((l + r) >> 1), x);
    else
      update(t[p].rs, ((l + r) >> 1) + 1, r, x);
  }
  int query(int p, int l, int r) {
    if (l >= ql && r <= qr) return t[p].sum;
    int res = 0;
    if (ql <= ((l + r) >> 1)) res += query(t[p].ls, l, ((l + r) >> 1));
    if (qr > ((l + r) >> 1)) res += query(t[p].rs, ((l + r) >> 1) + 1, r);
    return res;
  }

 public:
  inline void build(int n) {
    for (register int i = 1; i <= n; ++i)
      root[i] = root[i - 1], update(root[i], 1, inf, val[i]);
  }
  inline int query(int p1, int p2, int l, int r) {
    ql = l, qr = r;
    return query(root[p2], 1, inf) - query(root[p1 - 1], 1, inf);
  }
} T;
int p[maxn];
signed main() {
  int n, m, a, b, c, d;
  fin >> n;
  for (register int i = 1; i <= n; ++i) fin >> a, p[a] = i;
  for (register int i = 1; i <= n; ++i) fin >> a, val[p[a]] = i;
  T.build(n);
  fin >> m;
  while (m--) {
    fin >> a >> b >> c >> d;
    if (a > b) std::swap(a, b);
    if (c > d) std::swap(c, d);
    fout << T.query(a, b, c, d) << '\n';
  }
  return 0;
}
