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>

#define R register
#define ll long long
#define meow(cat...) fprintf(stderr, cat)
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 1e6 + 10;

struct node
{
    int sum;
    int lc, rc;
};

node t[MaxN << 5];
int n, m, cnt, ans, a[MaxN], b[MaxN], c[MaxN], id[MaxN], rt[MaxN];

struct SegmentTree
{
    void insert(int &rt, int pre, int l, int r, int pos)
    {
        rt = ++cnt, t[rt].sum = t[pre].sum + 1;
        t[rt].lc = t[pre].lc, t[rt].rc = t[pre].rc;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid)
            insert(t[rt].lc, t[pre].lc, l, mid, pos);
        else
            insert(t[rt].rc, t[pre].rc, mid + 1, r, pos);
    }
    int query(int u, int v, int l, int r, int ql, int qr)
    {
        if (l > qr || ql > r) return 0;
        if (ql <= l && r <= qr) return t[v].sum - t[u].sum;
        int mid = (l + r) >> 1;
        return query(t[u].lc, t[v].lc, l, mid, ql, qr) +
               query(t[u].rc, t[v].rc, mid + 1, r, ql, qr);
    }
} T;

int f(int z) { return (z + ans + n) % n + 1; }
int cmp(int a, int b) { return ::a[a] < ::a[b]; }

inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

signed main()
{
    n = read(), ans = -1;
    for (int i = 1; i <= n; i++)
        a[i] = read(), id[i] = i;
    for (int i = 1; i <= n; i++)
        b[i] = read(), c[i] = b[i];
    for (int i = 1; i <= n; i++)
    {
        b[i] = (id[i] + c[i] - a[i] + n) % n;
        if(!b[i]) b[i] = n;
    }
    for (int i = 1; i <= n; i++)
        T.insert(rt[i], rt[i - 1], 1, n, b[i]);
    m = read();
    while (m--)
    {
        int a = read(), b = read(), c = read(), d = read();
        int l = std::min(f(a), f(b)), r = std::max(f(a), f(b));
        int u = std::min(f(c), f(d)), v = std::max(f(c), f(d));
        printf("%d\n", (ans = T.query(rt[u - 1], rt[v], 1, n, l, r)));
    }
    return 0;
}
