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>
std::vector<int32_t>* segtree;
int32_t* data;
void build(int32_t node, int32_t left, int32_t right) {
  if (right - left == 1) {
    segtree[node] = {data[left]};
    return;
  }
  int32_t m = (left + right) / 2;
  build(node * 2 + 1, left, m);
  build(node * 2 + 2, m, right);
  segtree[node].resize(right - left);
  std::merge(segtree[node * 2 + 1].begin(), segtree[node * 2 + 1].end(),
             segtree[node * 2 + 2].begin(), segtree[node * 2 + 2].end(),
             segtree[node].begin());
}
int32_t query(int32_t node, int32_t left, int32_t right, int32_t query_left,
              int32_t query_right, int32_t param) {
  if (left >= query_right || right <= query_left) return 0;
  if (left >= query_left && right <= query_right)
    return std::lower_bound(segtree[node].begin(), segtree[node].end(), param) -
           segtree[node].begin();
  int32_t m = (left + right) / 2;
  return query(node * 2 + 1, left, m, query_left, query_right, param) +
         query(node * 2 + 2, m, right, query_left, query_right, param);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int32_t n;
  std::cin >> n;
  int32_t* arr1 = new int32_t[n];
  int32_t* arr2 = new int32_t[n];
  for (int32_t i = 0; i < n; i++) {
    std::cin >> arr1[i];
    arr1[i]--;
  }
  for (int32_t i = 0; i < n; i++) {
    std::cin >> arr2[i];
    arr2[i]--;
  }
  int32_t* positions_in_1 = new int32_t[n];
  int32_t* positions = new int32_t[n];
  for (int32_t i = 0; i < n; i++) positions_in_1[arr1[i]] = i;
  for (int32_t i = 0; i < n; i++) positions[positions_in_1[arr2[i]]] = i;
  segtree = new std::vector<int32_t>[4 * n];
  data = positions;
  build(0, 0, n);
  int32_t num_queries;
  std::cin >> num_queries;
  int32_t x = 0;
  for (int32_t i = 0; i < num_queries; i++) {
    int32_t a, b, c, d;
    std::cin >> a >> b >> c >> d;
    int32_t fa = (a - 1 + x) % n;
    int32_t fb = (b - 1 + x) % n;
    int32_t fc = (d - 1 + x) % n;
    int32_t fd = (c - 1 + x) % n;
    int32_t left1 = std::min(fa, fb), right1 = std::max(fa, fb);
    int32_t left2 = std::min(fc, fd), right2 = std::max(fc, fd);
    int32_t answer = query(0, 0, n, left1, right1 + 1, right2 + 1) -
                     query(0, 0, n, left1, right1 + 1, left2);
    std::cout << answer << "\n";
    x = answer + 1;
  }
  return 0;
};