Tarkastellaan kahta positiivista kokonaislukumuuttujaa $a$ ja $b$. Määrittelemme ”supistus”-operaation: $D(a, b)$ tarkoittaa muuttujan $a$ arvon muuttamista arvoksi $\frac{a}{\gcd(a,b)}$, kun taas muuttujan $b$ arvo pysyy ennallaan. Tässä $\gcd(a, b)$ tarkoittaa lukujen $a$ ja $b$ suurinta yhteistä tekijää. Esimerkiksi jos $a = 6$ ja $b = 10$, niin yhden $D(a, b)$-kutsun jälkeen muuttujan $a$ arvoksi tulee $3$ ja $b$ pysyy arvossa $10$.

Tarkastellaan puuta, jonka solmujen painot ovat positiivisia kokonaislukuja ja jossa solmun $i$ paino on $c_i$. Määrittelemme puussa ”ketjusupistus”-operaation: $T_{u,v}(a)$. Tässä $u$ ja $v$ ovat kaksi puun solmua ja $a$ on positiivinen kokonaislukumuuttuja. Oletetaan, että yksinkertainen polku solmusta $u$ solmuun $v$ puussa kulkee järjestyksessä solmujen $x_1, x_2, \dots, x_k$ kautta (missä $k \ge 1$, $x_1 = u$ ja $x_k = v$). Operaatio $T_{u,v}(a)$ tarkoittaa operaation $D(a, c_{x_i})$ suorittamista järjestyksessä alkaen arvosta $i = 1$ arvoon $k$, eli muuttujan $a$ arvon supistamista vaiheittain polun varrella olevien solmupainojen mukaisessa järjestyksessä.

Tarkastellaan puuta $R$, jossa on aluksi vain yksi solmu (numeroltaan $1$, solmupainoltaan $c_1$). Kasvattaaksesi sen $n$ solmun puuksi sinun tulee suorittaa $n - 1$ kasvuoperaatiota. $i$:nnessä operaatiossa annetaan kolme kokonaislukua $a_i, u_i, v_i$, missä $u_i$ ja $v_i$ ovat taatusti nykyisessä puussa jo olevia solmuja ja $a_i$ on positiivinen kokonaislukumuuttuja. Sinun tulee ensin suorittaa ketjusupistusoperaatio $T_{u_i,v_i}(a_i)$ ja sen jälkeen lisätä puuhun uusi solmu: tämän uuden solmun numero on $i + 1$, sen paino $c_{i+1}$ on muuttujan $a_i$ arvo ketjusupistuksen jälkeen, ja se yhdistetään solmuun $v_i$.

Tulosta lopuksi vastauksena kunkin solmun paino.

Syöte

Ensimmäisellä rivillä on kaksi positiivista kokonaislukua $n$ ja $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), jotka ilmaisevat, että on kasvatettava $n$ solmun puu, jonka ensimmäisen solmun alkupaino on $c_1$.

Toiselta riviltä $n$:nelle riville, $i$:nnellä rivillä on kolme positiivista kokonaislukua $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), jotka ilmaisevat, että kasvatetaan $i$:s solmu, joka yhdistetään solmuun $v_i$ ja jonka paino $c_i$ on tulos operaation $T_{u_i,v_i}(a_i)$ suorittamisesta luvulle $a_i$.

Tuloste

Tulosta yhdelle riville välilyönnein erotettuina $n$ positiivista kokonaislukua, jotka ilmaisevat painot $c_1, c_2, \dots, c_n$.

Esimerkki

Syöte 1

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

Tuloste 1

10 3 2 7 2