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 int maxn = 1000020;
const int max2n = 1050020;
const int MOd = 1e9 + 9;
int a, ar[maxn], bs[maxn], n;
vector<int> segment[maxn * 2];
int f(int n, int back) { return (n - 1 + back) % a + 1; }
int main() {
  scanf("%d", &a);
  n = 1;
  while (n < a) n *= 2;
  for (int i = 1; i <= a; i++) scanf("%d", &ar[i]);
  for (int i = 1, j; i <= a; i++) scanf("%d", &j), bs[j] = i;
  int b, z = 0;
  scanf("%d", &b);
  for (int i = n; i < n * 2; i++) segment[i].push_back(bs[ar[i - n + 1]]);
  for (int k = n - 1; k >= 1; k--) {
    ;
    for (int i = 0, j = 0;
         i < segment[2 * k].size() || j < segment[2 * k + 1].size();) {
      if (i == segment[2 * k].size())
        segment[k].push_back(segment[2 * k + 1][j++]);
      else if (j == segment[2 * k + 1].size())
        segment[k].push_back(segment[2 * k][i++]);
      else if (segment[2 * k][i] < segment[2 * k + 1][j])
        segment[k].push_back(segment[2 * k][i++]);
      else
        segment[k].push_back(segment[2 * k + 1][j++]);
    }
  }
  for (int i = 1; i <= b; i++) {
    int x1, x2, asseopirwjaelkf, asrwjaelkf;
    scanf("%d %d %d %d", &x1, &asseopirwjaelkf, &x2, &asrwjaelkf);
    x1 = f(x1, z);
    x2 = f(x2, z);
    asseopirwjaelkf = f(asseopirwjaelkf, z);
    asrwjaelkf = f(asrwjaelkf, z);
    if (x1 > asseopirwjaelkf) swap(x1, asseopirwjaelkf);
    if (x2 > asrwjaelkf) swap(x2, asrwjaelkf);
    z = 0;
    for (int l = x1 + n - 1, r = asseopirwjaelkf + n - 1; l <= r;
         l >>= 1, r >>= 1) {
      if (l & 1) {
        z += upper_bound(segment[l].begin(), segment[l].end(), asrwjaelkf) -
             lower_bound(segment[l].begin(), segment[l].end(), x2);
        l++;
      }
      if (!(r & 1)) {
        z += upper_bound(segment[r].begin(), segment[r].end(), asrwjaelkf) -
             lower_bound(segment[r].begin(), segment[r].end(), x2);
        r--;
      }
    }
    printf("%d\n", z);
  }
  return 0;
}
