Танд $n$ элементтэй $p$, $q$ сэлгэмэл болон $l_1$, $r_1$, $l_2$, $r_2$ ($l_1 ≤ r_1$; $l_2 ≤ r_2$) хэлбэрийн $m$ хүсэлт өгөгдсөн. Таны даалгавар бол $p$ сэлгэмлийн хувьд $[l_1, r_1]$ (зах нь орно) хэсэгт байгаа тоонууд болон $q$ $[l_2, r_2]$ (зах нь орно) хэсэгт байгаа тоонуудаас давхцаж байгаа тоо хэдэн ширхэг байгааг олох юм.

$n$ элементтэй сэлгэмэл гэдэг нь $n$ ширхэг ялгаатай, бүх элементийн утга нь $1$-с багагүй, $n$-с ихгүй байх тоон дараалал юм.

$g_1, g_2, ... , g_n$ дараалалд байгаа $v$ ($1 ≤ v ≤ n$) тооны байрлал нь $g_i = v$ байх $i$ индекс юм.

Оролт

Оролтын эхний мөрөнд $2$ сэлгэмлийн элементийн тоо $n$ ($1 ≤ n ≤ 10^6$) өгөгдөнө. Дараагийн мөрөнд $p$ сэлгэмлийн элементүүд $p_1, p_2, ... , p_n$ ($1 ≤ p_i ≤ n$) байна. Гуравдугаар мөрөнд $q$ сэлгэмлийн элементүүд $q_1, q_2, ... , q_n$ өгөгдөнө.

Дараагийн мөрөнд хүсэлтийн тоо $m$ ($1 ≤ m ≤ 2·10^5$).

Үүний дараа $m$ мөр бүрт хүсэлтүүдийг тодорхойлох өгөгдөл байрлана. $i$-р мөрөнд $a$, $b$, $c$, $d$ тоонууд өгөгдөх бөгөөд хүсэлтийн мэдээлэл болох $l_1, r_1$, $l_2$, $r_2$-г дараах байдлаар олно:

• Шинэ хувьсагч $x$-г тодорхойлно. Хэрвээ анхны хүсэлт бол утга нь $0$ байна. бусад тохиолдолд өмнөх хүсэлтэн дахь утгаасаа $1$-р их байна.
• $f(z) = ((z - 1 + x) \ mod \ n) + 1$ гэж тодорхойлъё.
• $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))$ тус тус байна.

Гаралт

Хүсэлт бүрийн хариуг нэр мөрөнд хэвлэ.