Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n, lst;
int ID[MAXN], rt[MAXN];
int Read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x * 10) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
void Put1(int x) {
  if (x > 9) Put1(x / 10);
  putchar(x % 10 ^ 48);
}
void Put(int x, char c = -1) {
  if (x < 0) putchar('-'), x = -x;
  Put1(x);
  if (c >= 0) putchar(c);
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Abs(T x) {
  return x < 0 ? -x : x;
}
struct Chairman_Tree {
  int tot;
  struct node {
    int l, r, val;
  } t[MAXN * 24];
  void Add(int lrt, int &rt, int ID, int l, int r) {
    rt = ++tot;
    t[rt] = t[lrt];
    t[rt].val++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (ID <= mid)
      Add(t[lrt].l, t[rt].l, ID, l, mid);
    else
      Add(t[lrt].r, t[rt].r, ID, mid + 1, r);
  }
  int Query(int x, int l, int r, int ql, int qr) {
    if (!x) return 0;
    if (ql <= l && r <= qr) return t[x].val;
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid) ret += Query(t[x].l, l, mid, ql, qr);
    if (mid + 1 <= qr) ret += Query(t[x].r, mid + 1, r, ql, qr);
    return ret;
  }
} ct;
int f(int z) { return (z - 1 + lst) % n + 1; }
int main() {
  n = Read();
  for (int i = 1; i <= n; ++i) ID[Read()] = i;
  for (int i = 1; i <= n; ++i) ct.Add(rt[i - 1], rt[i], ID[Read()], 1, n);
  for (int Q = Read(); Q; --Q) {
    int a = Read(), b = Read(), c = Read(), d = Read();
    int l1 = Min(f(a), f(b)), r1 = Max(f(a), f(b)), l2 = Min(f(c), f(d)),
        r2 = Max(f(c), f(d));
    Put(lst = (ct.Query(rt[r2], 1, n, l1, r1) -
               ct.Query(rt[l2 - 1], 1, n, l1, r1)),
        '\n');
    lst++;
  }
  return 0;
}