Две перестановки

Вам даны две перестановки из n элементов и m запросов вида: l_1, r_1, l_2, r_2.

Ответом на запрос является количество чисел от 1 до n таких, что их позиция в первой перестановке находится в отрезке [l_1, r_1], а позиция во второй перестановке — в отрезке [l_2, r_2].

Входные данные

В первой строке находится одно целое число n (1 ≤ n ≤ 10^6) — количество элементов в обеих перестановках. В следующей строке находятся n чисел, разделенных пробелами: a_1, a_2, ..., a_n (1 ≤ a_i ≤ _n) — элементы первой перестановки. В следующей строке находится вторая перестановка в таком же формате.

В следующей строке находится одно целое число m (1 ≤ m ≤ 10^5) — количество запросов.

В следующих m строках находятся описания запросов по одному в строке. Описание i-того запроса состоит из четырех чисел: a, b, c, d (1 ≤ a, b, c, d ≤ n). Параметры запроса l_1, r_1, l_2, r_2 получаются из чисел a, b, c, dследующим образом:

1. Введем переменную x. Если запрос первый, то она равна 0, иначе она равна ответу на предыдущий запрос плюс один.

2. Введем функцию f(z) = ((z 1 + x) mod n) + 1.

3. Число a заменим на f(a), число b заменим на f(b), число c заменим на f(c), число d заменим на f(d).

4. Положим l_1 = min(a, b), r_1 = max(a, b), l_2 = min(c, d), r_2 = max(c, d).

Выходные данные

Для каждого запроса выведите одно число в отдельной строке — ответ на запрос.

Примеры