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;
inline int Get_Int() {
  int Num = 0, Flag = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') Flag = -Flag;
  } while (ch < '0' || ch > '9');
  do {
    Num = Num * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return Num * Flag;
}
int N, Q, LastAns = -1;
int A[1000005], B[1000005], Position[1000005];
namespace Segment_Tree {
vector<int> Nodes[1000005 * 4];
void Build(int x, int Left, int Right) {
  if (Left == Right) {
    Nodes[x].push_back(Position[A[Left]]);
    return;
  }
  int Mid = Left + Right >> 1;
  Build(x << 1, (0 ? Mid + 1 : Left), (0 ? Right : Mid));
  Build(x << 1 | 1, (1 ? Mid + 1 : Left), (1 ? Right : Mid));
  vector<int>::iterator it1 = Nodes[x << 1].begin(),
                        it2 = Nodes[x << 1 | 1].begin();
  while (it1 != Nodes[x << 1].end() || it2 != Nodes[x << 1 | 1].end()) {
    if (it1 == Nodes[x << 1].end())
      Nodes[x].push_back(*it2++);
    else if (it2 == Nodes[x << 1 | 1].end())
      Nodes[x].push_back(*it1++);
    else if (*it1 < *it2)
      Nodes[x].push_back(*it1++);
    else
      Nodes[x].push_back(*it2++);
  }
}
int Query(int x, int left, int right, int l, int r, int Left, int Right) {
  if (left == Left && right == Right)
    return upper_bound(Nodes[x].begin(), Nodes[x].end(), r) -
           lower_bound(Nodes[x].begin(), Nodes[x].end(), l);
  int Mid = Left + Right >> 1;
  if (left > Mid || right <= Mid) {
    int i = left > Mid;
    return Query(x << 1 | i, left, right, l, r, (i ? Mid + 1 : Left),
                 (i ? Right : Mid));
  }
  return Query(x << 1, left, Mid, l, r, (0 ? Mid + 1 : Left),
               (0 ? Right : Mid)) +
         Query(x << 1 | 1, Mid + 1, right, l, r, (1 ? Mid + 1 : Left),
               (1 ? Right : Mid));
}
}  // namespace Segment_Tree
inline int F(int x) { return (x + LastAns) % N + 1; }
int main() {
  cin >> N;
  for (int i = 1; i <= N; ++i) A[i] = Get_Int();
  for (int i = 1; i <= N; ++i) {
    B[i] = Get_Int();
    Position[B[i]] = i;
  }
  Segment_Tree::Build(1, 1, N);
  cin >> Q;
  while (Q--) {
    int a = Get_Int(), b = Get_Int(), c = Get_Int(), d = Get_Int();
    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));
    printf("%d\n", LastAns = Segment_Tree::Query(1, L1, R1, L2, R2, 1, N));
  }
  return 0;
}