Cum protagonistul nostru, Sorin Pastrama, este seful la bani, acesta isi doreste sa plece in tari straine. Toata lumea stie ca acesta se respecta, asa ca el a ales cea mai de lux companie aeriana si a zis ca va calatori numai cu aceasta. Compania opereaza in $N$ orase mari ale lumii, cu diferite zboruri intre acestea. Mai exact, aceste rute constituie un arbore cu $N$ noduri, cu radacina in nodul $1$, fiecare muchie (cate un zbor in ambele sensuri) avand cate un cost. Cum Pastrama nu este foarte bun la matematica (deoarece el a urmat scoala de smecherie), va roaga sa-l ajutati cu urmatoarele $M$ operatii:
* $1 x c$ -> costul muchiei de la $x$ la tatal lui $x$ devine $c$ ( $2 ≤ x ≤ N$ )

* $2 x y$ -> Pastrama vrea sa plece din nodul $x$ si sa ajunga in nodul $y$. La fiecare pas, daca el se afla intr-un nod anume diferit de $y$, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori **( $y$ este un stramos al lui $x$ )**

* $2 x y$ -> Pastrama vrea sa plece din nodul $x$ si sa ajunga in nodul $y$. La fiecare pas, daca el se afla intr-un nod anume diferit de $y$, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo, platind costul aferent desigur. Va repeta acest lucru pana va ajunge in nodul $y$. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatorii **( $y$ este un stramos al lui $x$ )**

h2. Date de intrare

* $1 ≤ N, M ≤ 10^5^$
* $1 ≤ costul unei muchii ≤ 10^6^$
* **La operatia de tipul $2$, nodul $y$ este un stramos al nodului $x$**

* Pastrama plateste pentru placerile sale, iar de aceea compania de lux pe care si-a ales-o are numai avioane americane

* Pastrama plateste pentru placerile sale, iar de aceea compania de lux pe care si-a ales-o detine numai avioane americane

h2. Exemplu