== include(page="template/taskheader" task_id="arbquery") ==

== include(page="template/taskheader" task_id="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.

* 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], ..., 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], .. , V[N], V[1], .. , V[R]$ care sunt egale cu $X$
 

* Query $L$ $R$ $X$: câte numere din şir, din subsecvenţa <tex> V_L, V_{L+1}, ... , V_R </tex> sunt egale cu $X$. Pot exista query-uri în care $L > R$ caz în care vrem numărul de numere din <tex> V_L, ... , V_N, V_1, ... , V_R </tex> care sunt egale cu $X$

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

Primul rând al fişierului de intrare $arbquery.out$ conţine numărele $N$ şi $Q$. Urmează $N - 1$ rânduri, fiecare conţinând trei valori $x, y, l$, ce indică existenţa unei muchii de la $x$ la $y$ cu lungimea $l$. Urmează apoi $Q$ linii, fiecare conţinând două valori $x, y$, ce reprezintă o interogare asupra lanţului unic de la $x$ la $y$.

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$

h2. Date de ieşire

Fişierul de ieşire $arbquery.out$ conţine răspunsurile celor $Q$ interogări, în ordine.

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

h2. Subtaskuri
* *Subtask 1 (10 puncte)*

** $N, Q ≤ 20$.
** Oricare muchie are lungimea cel mult $10^5^$.

** $1 ≤ N ≤ 1.000.$
** $1 ≤ M ≤ 1.000.$

* *Subtask 2 (30 puncte)*

** $N, Q ≤ 2.000$.
** Oricare muchie are lungimea cel mult $10^5^$.

** $1 ≤ N ≤ 100.000.$
** $1 ≤ M ≤ 100.000.$
** Nu există operaţii de tipul 1.
 
* *Subtask 3 (30 puncte)*
** $1 ≤ N ≤ 100.000$
** $1 ≤ M ≤ 100.000$
** Nu există operaţii de tipul 2.
 
* *Subtask 4 (30 puncte)*
** $1 ≤ N ≤ 100.000$
** $1 ≤ M ≤ 100.000$

* *Subtask 3 (10 puncte)*
** $N, Q ≤ 100.000$.
** Oricare nod are cel mult 2 muchii incidente.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 4 (10 puncte)*
** $N, Q ≤ 100.000$.
** Cel mult un nod are mai mult de 1 muchie incidentă.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 5 (40 puncte)*
** $N, Q ≤ 100.000$.
** Oricare muchie are lungimea cel mult $10^5^$.

h2. Exemplu

table(Exemplu). |_. hiperquery.in |_. hiperquery.out |
| 3 3
1 2 1
2 3 100
1 2
2 3
1 3
| 102
201
303

table(example). |_. hiperquery.in |_. hiperquery.out |
| 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
| 2
  1
  2
  1

|

Observăm că sunt trei lanţuri, $1 - 2$ de cost 1, $2 - 3$ de cost $100$ şi $1 - 2 - 3$ de cost $101$. Astfel $d(1, 2) = 102, d(2, 3) = 201$. Astfel rezultatul pentru $1, 2$ este $d(1, 2) = 102$, pentru $2, 3$ este $d(2, 3) = 201$, şi pentru $1, 3$ este $d(1, 2) + d(2, 3) = 303$.

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]$
 

== include(page="template/taskfooter" task_id="arbquery") ==

== include(page="template/taskfooter" task_id="hiperquery") ==