D. Сэрэга ба хөгжилдөөн

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сэрэга хөгжилдөх дуртай. Гэхдээ хүн бүр л өөр өөрөөр хөгжилддөг шүү дээ. Сэрэга хүсэлттэй бодлого бодож хөгжилддөг. Нэгэн өдөр Фэдор бодлого дэвшүүлжээ.

Чамд $n$ урттай бүхэл тоон дараалал $a$ болон үүн дээрх хүсэлт өгөгджээ. Хүсэлт хоёр янз:

  1. $l$-ээс $r$ дугаар хүртэлх гишүүдийг баруун тийш нэг удаа тойрог хэлбэрээр хөдөлгөнө. Өөрөөр хэлбэл $a[l], a[l + 1], ..., a[r - 1], a[r] -> a[r], a[l], a[l + 1], ..., a[r - 1]$ гэж хувиргах юм.
  2. $l$-ээс $r$ дугаар хүртэлх гишүүдийн хэд нь $k$-тай тэнцүү болохыг ол.

Фэдор энэ бодлогоо Сэрэгад үзүүлэхээр ихэд яарав. Сэрэга ч тун хурдан бодож гэнэ. Харин чи бодож чадах уу?

Оролт

Эхний мөрөнд дарааллын уртыг илэрхийлэх $n$ ($1 ≤ n ≤ 10^{5}$) гэсэн бүхэл тоо байна. Хоёр дахь мөрөнд дарааллын гишүүдийг илэрхийлэх $a[1], a[2], ..., a[n]$ ($1 ≤ a[i] ≤ n$) тоонууд байна.

Гурав дахь мөрөнд хүсэлтийн тоог илэрхийлэх $q$ ($1 ≤ q ≤ 10^{5}$) тоо байна. Дараагийн $q$ мөрөнд хүсэлтүүд байна.

Хүсэлтэд онлайнаар хариулж байгаа тул хүсэлт нууцлагдсан байна. Эхний төрлийн хүсэлт дараахь хэлбэртэй өгөгдөнө: $1$ $l'_{i}$ $r'_{i}$. Хоёр дахь төрлийн хүсэлт дараахь хэлбэртэй өгөгдөнө: $2$ $l'_{i}$ $r'_{i}$ $k'_{i}$. Өгөгдөлд буй тоо бүр бүхэл тоо байна. Мөн $1 ≤ l'_{i}, r'_{i}, k'_{i} ≤ n$ байна.

Нууцлагдсан хүсэлтийг тайлахын тулд дараахь алхмуудыг хийх ёстой:

$l_{i} = ((l'_{i} + сүүлийн хариу - 1) mod n) + 1; r_{i} = ((r'_{i} + сүүлийн хариу - 1) mod n) + 1; k_{i} = ((k'_{i} + сүүлийн хариу - 1) mod n) + 1.$

Энд сүүлийн хариу гэдэг нь хамгийн сүүлийн хоёрдугаар төрлийн хүсэлтийн хариу юм. (Эхлээд сүүлийн хариу = 0 байна). Хэрэв $l_{i}$ нь $r_{i}$-ээс их болчихвол утгуудыг нь солих ёстой.

Гаралт

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

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
7
6 6 2 7 4 2 5
7
1 3 6
2 2 4 2
2 2 4 7
2 2 2 5
1 2 6
1 1 4
2 1 7 3
Гаралт
2
1
0
0
Оролт
8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5
Гаралт
2
0
Сэтгэгдлүүдийг ачааллаж байна...