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, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then 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 ACM-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

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-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/30/2017 09:35:28 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|