Дві перестановки
Вам задано дві перестановки з 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 наступним чином:
Введемо змінну x. Якщо запит перший, то вона дорівнює 0, інакше вона дорівнює відповіді на попередній запит плюс один.
Введемо функцію f(z) = ((z 1 + x) mod n) + 1.
Число a замінимо на f(a), число b замінимо на f(b), число c замінимо на f(c), число d замінимо на f(d).
Покладемо l_1 = min(a, b), r_1 = max(a, b), l_2 = min(c, d), r_2 = max(c, d).
Вихідні дані
Для кожного запиту виведіть одне число у окремому рядку — відповідь на запит.