Lítum á tvær jákvæðar heiltölubreytur $a$ og $b$. Við skilgreinum „styttingar“-aðgerð: $D(a, b)$ þýðir að breyta gildi breytunnar $a$ í $\frac{a}{\gcd(a,b)}$, á meðan gildi $b$ helst óbreytt. Hér táknar $\gcd(a, b)$ grootste samdeili $a$ og $b$. Til dæmis, ef $a = 6$ og $b = 10$, þá verður gildi $a$ jafnt $3$ eftir eitt kall á $D(a, b)$, en $b$ helst $10$.

Lítum á tré með jákvæðum heiltöluþyngdum á hnútum, þar sem þyngd hnúts $i$ er $c_i$. Við skilgreinum „keðjustyttingar“-aðgerð á trénu: $T_{u,v}(a)$. Hér eru $u$ og $v$ tveir hnútar í trénu og $a$ er jákvæð heiltölubreyta. Gerum ráð fyrir að einfaldi vegurinn frá $u$ til $v$ í trénu fari í röð í gegnum hnútana $x_1, x_2, \dots, x_k$ (þar sem $k \ge 1$, $x_1 = u$ og $x_k = v$). Aðgerðin $T_{u,v}(a)$ felst í því að framkvæma aðgerðina $D(a, c_{x_i})$ í röð frá $i = 1$ til $k$, það er að segja að stytta gildi breytunnar $a$ í röð eftir þyngdum hnútanna á veginum.

Lítum á tré $R$ sem í upphafi inniheldur aðeins einn hnút (merktan $1$, með þyngd $c_1$). Til að láta það vaxa í tré með $n$ hnútum þarftu að framkvæma $n - 1$ vaxtaraðgerðir. Í $i$-tu aðgerðinni eru gefnar þrjár heiltölur $a_i, u_i, v_i$, þar sem tryggt er að $u_i$ og $v_i$ séu hnútar sem eru þegar í trénu, og $a_i$ er jákvæð heiltölubreyta. Þú þarft fyrst að framkvæma keðjustyttingaraðgerðina $T_{u_i,v_i}(a_i)$ og bæta síðan nýjum hnúti við tréð: þessi nýi hnútur fær númerið $i + 1$, þyngd hans $c_{i+1}$ er gildi $a_i$ eftir keðjustyttinguna, og hann er tengdur við hnút $v_i$.

Að lokum skaltu prenta út þyngdir allra hnúta sem svar.

Inntak

Fyrsta línan inniheldur tvær jákvæðar heiltölur $n$ og $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), sem tákna að rækta þurfi tré með $n$ hnútum þar sem upphafsþyngd fyrsta hnútsins er $c_1$.

Frá annarri línu til $n$-tu línu inniheldur $i$-ta línan þrjár jákvæðar heiltölur $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), sem gefa til kynna að $i$-ti hnúturinn vaxi, tengist hnúti $v_i$, og þyngd hans $c_i$ sé útkoman úr því að framkvæma aðgerðina $T_{u_i,v_i}(a_i)$ á $a_i$.

Úttak

Prentaðu eina línu sem inniheldur $n$ jákvæðar heiltölur, aðskildar með bilum, sem tákna þyngdirnar $c_1, c_2, \dots, c_n$.

Dæmi

Inntak 1

5 10
6 1 1
2 2 2
35 1 2
84 3 4

Úttak 1

10 3 2 7 2