Betrakt to positive heltallsvariabler $a$ og $b$. Vi definerer en «reduksjons»-operasjon: $D(a, b)$ betyr å endre verdien til variabelen $a$ til $\frac{a}{\gcd(a,b)}$, mens verdien til $b$ forblir uendret. Her betegner $\gcd(a, b)$ den største felles divisoren til $a$ og $b$. For eksempel, hvis $a = 6$ og $b = 10$, vil verdien til $a$ bli $3$ etter ett kall til $D(a, b)$, mens $b$ forblir $10$.

Betrakt et tre med positive heltallsvekter på nodene, der nodevekten til node $i$ er $c_i$. Vi definerer en «kjedereduksjons»-operasjon på treet: $T_{u,v}(a)$. Her er $u$ og $v$ to noder i treet, og $a$ er en positiv heltallsvariabel. Anta at den enkle stien fra $u$ til $v$ i treet besøker nodene $x_1, x_2, \dots, x_k$ i rekkefølge (der $k \ge 1$, $x_1 = u$ og $x_k = v$). Operasjonen $T_{u,v}(a)$ betyr å utføre operasjonen $D(a, c_{x_i})$ i rekkefølge fra $i = 1$ til $k$, det vil si å redusere verdien til variabelen $a$ sekvensielt ved hjelp av nodevektene langs stien.

Betrakt et tre $R$ som til å begynne med bare inneholder én node (med nummer $1$ og nodevekt $c_1$). For å la det vokse til et tre med $n$ noder, må du utføre $n - 1$ vekstoperasjoner. I den $i$-te operasjonen gis tre heltall $a_i, u_i, v_i$, der $u_i$ og $v_i$ garantert er noder som allerede finnes i det nåværende treet, og $a_i$ er en positiv heltallsvariabel. Du må først utføre kjedereduksjonsoperasjonen $T_{u_i,v_i}(a_i)$, og deretter legge til en ny node i treet: denne nye noden får nummeret $i + 1$, dens vekt $c_{i+1}$ er verdien til $a_i$ etter kjedereduksjonen, og den kobles til node $v_i$.

Til slutt skal du skrive ut nodevektene til hver node som svar.

Inndata

Den første linjen inneholder to positive heltall $n$ og $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), som representerer behovet for å dyrke et tre med $n$ noder, der startvekten til den første noden er $c_1$.

Fra den andre til den $n$-te linjen inneholder den $i$-te linjen tre positive heltall $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), som angir at den $i$-te noden vokser frem, kobles til node $v_i$, og at dens vekt $c_i$ er resultatet av å utføre operasjonen $T_{u_i,v_i}(a_i)$ på $a_i$.

Utdata

Skriv ut én linje som inneholder $n$ positive heltall, adskilt med mellomrom, som representerer vektene $c_1, c_2, \dots, c_n$.

Eksempel

Inndata 1

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

Utdata 1

10 3 2 7 2