Hiperquery

Se dă un şir circular de numere naturale $V$ de lungime $N$, indexat de la $1$. Numerele din şir se află în intervalul închis $[1, N]$, iar prima şi ultima poziţie sunt considerate adiacente.

Sunt definite următoarele operaţii:

• Update $X$ $Y$: elementul de pe poziţia $X$ devine $Y$;
• Rotate $X$: roteşte spre dreapta şirul cu $X$ poziţii (şirul $[1, 2, 3, 4]$ rotit cu o poziţie spre dreapta devine $[4, 1, 2, 3]$);
• Query $L$ $R$ $X$: câte numere din şir, din subsecvenţa $V_L, V_{L+1}, \dots, V_R$ sunt egale cu $X$. Pot exista query-uri în care $L > R$, caz în care vrem numărul de numere din $V_L, \dots, V_N, V_1, \dots, V_R$ care sunt egale cu $X$.

Cerință

Dându-se şirul iniţial se cere să se proceseze un şir de operaţii dat.

Date de intrare

Pe prima linie a fişierului de intrare hiperquery.in se găseşte numărul $N$.

Pe următoarea linie se află $N$ numere naturale care formează şirul $V$.

Pe următoarea linie se află un număr $M$ urmat de $M$ linii pe care sunt descrise operaţiile date:

• Pentru update: 1 X Y
• Pentru rotire: 2 X
• Pentru query: 3 L R X

Date de ieșire

În fişierul de ieşire hiperquery.out se vor găsi răspunsurile la întrebări, fiecare pe câte un rând.

Restricții și precizări

Exemplu

hiperquery.in

4
4 1 3 1
6
3 2 4 1
3 3 1 4
3 3 2 1
1 1 2
2 2
3 1 1 3

hiperquery.out

2
1
2
1

Explicație

Pentru prima întrebare subsecvenţa este $[4, 1, 3, 1]$.

Pentru a doua întrebare subsecvenţa este $[4, 1, 3, 1]$.

Pentru a treia întrebare subsecvenţa este întreg şirul.

După primul update şirul devine $[2,1,3,1]$.

Dupa rotire şirul devine $[3,1,2,1]$.

Pentru ultima întrebare subsecvenţa este $[3,1,2,1]$.