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

** $1 \leq N \leq 1.000.$
** $1 \leq M \leq 1.000.$

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

* *Subtask 2 (35 puncte)*
** $1 \leq N \leq 100.000.$
** $1 \leq M \leq 100.000.$

* *Subtask 2 (30 puncte)*
** $1 ≤ N ≤ 100.000.$
** $1 ≤ M ≤ 100.000.$

** Nu există operaţii de tipul 1.

* *Subtask 3 (35 puncte)*
** $1 \leq N \leq 100.000$
** $1 \leq M \leq 100.000$

* *Subtask 3 (30 puncte)*
** $1 ≤ N ≤ 100.000$
** $1 ≤ M ≤ 100.000$

** Nu există operaţii de tipul 2.

* *Subtask 4 (20 puncte)*
** $1 \leq N \leq 100.000$
** $1 \leq M \leq 100.000$

* *Subtask 4 (30 puncte)*
** $1 ≤ N ≤ 100.000$
** $1 ≤ M ≤ 100.000$

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

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

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="hiperquery") ==