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;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a > b ? a : b;
  if (c != -1234567) ans = max1(ans, c);
  if (d != -1234567) ans = max1(ans, d);
  return ans;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs1(a - b) / abs1(a) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 1000110;
template <class t>
struct segment_node {
  int be, en;
  vector<int> arr;
};
template <class t>
struct segment_tree {
  int l;
  segment_node<t> tree[maxn * 4];
  inline int gleft(int no) { return no << 1; }
  inline int gright(int no) { return (no << 1) + 1; }
  inline int gfa(int no) { return no >> 1; }
  inline segment_tree() { l = 0; }
  void build(int no, int l, int r, t *a = NULL) {
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].arr.push_back(a[l]);
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    build(gleft(no), l, mid, a);
    build(gright(no), mid + 1, r, a);
    vector<int>::iterator it1 = tree[gleft(no)].arr.begin(),
                          it2 = tree[gright(no)].arr.begin(),
                          en1 = tree[gleft(no)].arr.end(),
                          en2 = tree[gright(no)].arr.end();
    for (; it1 != en1 && it2 != en2; it1++) {
      for (; it2 != en2 && *it2 <= *it1; it2++) tree[no].arr.push_back(*it2);
      tree[no].arr.push_back(*it1);
    }
    for (; it1 != en1; it1++) tree[no].arr.push_back(*it1);
    for (; it2 != en2; it2++) tree[no].arr.push_back(*it2);
  }
  t getsum(int l, int r, int no, int sm, int big) {
    if (l > r) return 0;
    if (l <= tree[no].be && r >= tree[no].en)
      return find(big, tree[no].arr.begin(), tree[no].arr.size(), 1, 0) -
             find(sm, tree[no].arr.begin(), tree[no].arr.size(), 0, 1) + 1;
    t ans = 0;
    int mid = (tree[no].be + tree[no].en) / 2;
    if (r >= tree[no].be && l <= mid)
      ans += getsum(max1(l, tree[no].be), min1(r, mid), gleft(no), sm, big);
    if (r >= mid + 1 && l <= tree[no].en)
      ans +=
          getsum(max1(l, mid + 1), min1(r, tree[no].en), gright(no), sm, big);
    return ans;
  }
};
segment_tree<int> sgt;
int n, nq;
int orig[maxn], arr[maxn], trans[maxn];
inline int func(int z, int x) { return (z - 1 + x) % n + 1; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", orig + i);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    trans[a] = i;
  }
  for (int i = 0; i < n; i++) arr[i] = trans[orig[i]];
  sgt.build(1, 0, n - 1, arr);
  scanf("%d", &nq);
  for (int i = 0, x = 0; i < nq; i++) {
    int a, b, c, d, l1, r1, l2, r2;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    l1 = min(func(a, x), func(b, x)) - 1, r1 = max(func(a, x), func(b, x)) - 1;
    l2 = min(func(c, x), func(d, x)) - 1, r2 = max(func(c, x), func(d, x)) - 1;
    printf("%d\n", x = sgt.getsum(l1, r1, 1, l2, r2));
    x++;
  }
  return 0;
}
