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

Poveste şi cerinţă...

Recent, s-a descoprit o noua insula numita Ostrov. Initial, aceasta insula nu are niciun oras sau strada construita. Datorita proprietatilor sale geografice extraordinare, multi actionari vor sa investeasca in aceasta insula pentru a-si construi fabrici de apa magica. Astfel, exista $Q$ operatii de forma:
* $0$ -> se construieste orasul $++N$
* $1 X nr m$ iar pe urmatoarele $m$ linii cate $3$ numere $x, y, s$ ce reprezinta o strada bidirectionala intre orasele $x$ si $y$ de cost $s$, $x$ si $y$ apartinand celor $nr$ orase construite reunit cu orasul $X$  -> proprietarul orasului $X$ construieste inca $nr$ orase (orasele de la $N+1$ la $N+nr$) care sunt legate intre ele (orasul $X$ cu cele $nr$ orase noi) prin cele $m$ strazi bidirectionale mentionate mai sus. Dupa aceasta operatie $N+=nr$
* &2 x y s$ -> pentru ca nu se poate ajunge din orasul $x$ in orasul $y$, investitorii care detin aceste doua orase colaboreaza si construiesc o strada bidirectionala intre orasele $x$ si $y$ de cost $s$
* $3 x y s$ -> costul strazii dintre orasele $x$ si $y$ devine $s$. Se garanteaza ca strada dintre $x$ si $y$ a fost construita anterior
* $4 x y$ -> sa se afiseze costul minim al unui drum de la orasul $x$ la orasul $y$, sau $-1$ daca nu se poate ajunge de la orasul $x$ la orasul $y$
 

h2. Date de intrare

Fişierul de intrare $ostrov.in$ ...

Fişierul de intrare $ostrov.in$ contine pe pe prima linie numarul $Q$, iar dupa aceea cele Q operatii de forma celor de mai sus.

h2. Date de ieşire

În fişierul de ieşire $ostrov.out$ ...

În fişierul de ieşire $ostrov.out$ sa se afiseze raspunsul pentru fiecare operatie de tipul 4 pe cate o linie separata.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $la final N ≤ 100000$
* $la final numarul de strazi ≤ 300000$
* $nr ≤ 10$
* $numarul operatiilor de tipul 3 $le; 10000$
* $numarul operatiilor de tipul 4 $le; 300000$

h2. Exemplu