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;
int X, N;
int func(int a) {
  a += X;
  a--;
  a %= N;
  if (a < 0) a += N;
  return a + 1;
}
int first_ar[1000000 + 9];
int second_ar[1000000 + 9];
int POS[1000000 + 9];
int KEEP[1000000 + 9];
vector<int> seg_tree[1000000 * 4 + 9];
void init_tree(int node, int beg, int end) {
  if (beg == end) {
    seg_tree[node].push_back(KEEP[beg]);
    return;
  }
  int mid = (beg + end) >> 1;
  init_tree((node << 1), beg, mid);
  init_tree((node << 1) | 1, mid + 1, end);
  for (int i = 0; i < seg_tree[(node << 1)].size(); i++)
    seg_tree[node].push_back(seg_tree[(node << 1)][i]);
  for (int i = 0; i < seg_tree[(node << 1) | 1].size(); i++)
    seg_tree[node].push_back(seg_tree[(node << 1) | 1][i]);
  sort(seg_tree[node].begin(), seg_tree[node].end());
  ;
}
int query(int node, int beg, int end, int i, int j, int a, int b) {
  if (i > end || j < beg) return 0;
  if (beg >= i && end <= j) {
    int ub = upper_bound(seg_tree[node].begin(), seg_tree[node].end(), b) -
             seg_tree[node].begin();
    int lb = lower_bound(seg_tree[node].begin(), seg_tree[node].end(), a) -
             seg_tree[node].begin();
    return ub - lb;
  }
  int mid = (beg + end) >> 1;
  int leftnode = query((node << 1), beg, mid, i, j, a, b);
  int rightnode = query(((node << 1) | 1), mid + 1, end, i, j, a, b);
  return (leftnode + rightnode);
}
int main() {
  int i, j, k, l, n, m, tot, temp, curr, val, prev, a, b, c, t, ans, cnt, x, y,
      siz, ii, jj, xx, yy, root, ind, len, q, xxx, yyy, d, r, no_per_blk;
  int l1, l2, r1, r2;
  cin >> n;
  N = n;
  for (i = 1; i <= n; i++) scanf("%d", &first_ar[i]);
  for (i = 1; i <= n; i++) POS[first_ar[i]] = i;
  for (i = 1; i <= n; i++) scanf("%d", &second_ar[i]);
  for (i = 1; i <= n; i++) KEEP[i] = POS[second_ar[i]];
  init_tree(1, 1, n);
  cin >> m;
  while (m--) {
    scanf("%d%d%d%d", &a, &b, &c, &d);
    l1 = min(func(a), func(b));
    r1 = max(func(a), func(b));
    l2 = min(func(c), func(d));
    r2 = max(func(c), func(d));
    ans = query(1, 1, n, l2, r2, l1, r1);
    printf("%d\n", ans);
    X = ans + 1;
  }
}