eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 5 секунд
Ліміт використання пам'яті 512 MiB

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

Відповіддю на запит є кількість чисел від 1 до n таких, що їх позиція у першій перестановці знаходиться у відрізку [l_1, r_1], а позиція у другій перестановці — у відрізку [l_2, r_2].

Вхідні дані

У першому рядку знаходиться одне ціле число n (1n10^6) — кількість елементів у обох перестановках. У наступному рядку знаходяться n чисел, відокремлених пропусками: a_1, a_2, ..., a_n (1a_i ≤ _n) — елементи першої перестановки. У наступному рядку знаходиться друга перестановка у такому ж форматі.

У наступному рядку знаходиться одне ціле число m (1m10^5) — кількість запитів.

У наступних m рядках знаходяться описи запитів по одному у рядку. Опис i-го запиту складається з чотирьох чисел: a, b, c, d (1a, b, c, dn). Параметри запиту 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).

Вихідні дані

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

Приклад

Вхідні дані #1
3
3 1 2
3 2 1
1
1 2 3 3
Вихідні дані #1
1
Джерело Зимова школа Харків 2013, День 6 - Г.Агапова та І.Фефера