h2. Date de intrare

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

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

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

h2. 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.

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

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

** $1 \leq N \leq 1.000.$
** $1 \leq M \leq 1.000.$
 
* *Subtask 2 (35 puncte)*
** $1 \leq N \leq 100.000.$
** $1 \leq M \leq 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$
** Nu există operaţii de tipul 2.
 
* *Subtask 4 (20 puncte)*
** $1 \leq N \leq 100.000$
** $1 \leq M \leq 100.000$

** $N, Q ≤ 20$.
** Oricare muchie are lungimea cel mult $10^5^$.
* *Subtask 2 (30 puncte)*
** $N, Q ≤ 2.000$.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *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