The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Two permutations

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given two permutations *p* and *q*, consisting of *n* elements, and *m* queries of the form: *l*_{1}, *r*_{1}, *l*_{2}, *r*_{2} (*l*_{1} ≤ *r*_{1}; *l*_{2} ≤ *r*_{2}). 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 [*l*_{1}, *r*_{1}] (borders included), and position in the second permutation is in segment [*l*_{2}, *r*_{2}] (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 *g*_{1}, *g*_{2}, ..., *g*_{n} is such number *i*, that *g*_{i} = *v*.

Input

The first line contains one integer *n* (1 ≤ *n* ≤ 10^{6}), the number of elements in both permutations. The following line contains *n* integers, separated with spaces: *p*_{1}, *p*_{2}, ..., *p*_{n} (1 ≤ *p*_{i} ≤ *n*). These are elements of the first permutation. The next line contains the second permutation *q*_{1}, *q*_{2}, ..., *q*_{n} in same format.

The following line contains an integer *m* (1 ≤ *m* ≤ 2·10^{5}), 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 *l*_{1}, *r*_{1}, *l*_{2}, *r*_{2} are obtained from the numbers *a*, *b*, *c*, *d* using the following algorithm:

- 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. - Introduce function
*f*(*z*) = ((*z*- 1 +*x*)*mod**n*) + 1. - Suppose
*l*_{1}=*min*(*f*(*a*),*f*(*b*)),*r*_{1}=*max*(*f*(*a*),*f*(*b*)),*l*_{2}=*min*(*f*(*c*),*f*(*d*)),*r*_{2}=*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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2022 04:28:37 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|