Betrakta två positiva heltalsvariabler $a$ och $b$. Vi definierar en "reduktions"-operation: $D(a, b)$ innebär att värdet på variabeln $a$ ändras till $\frac{a}{\gcd(a,b)}$, medan värdet på $b$ förblir oförändrat. Här betecknar $\gcd(a, b)$ den största gemensamma delaren till $a$ och $b$. Till exempel, om $a = 6$ och $b = 10$, så blir värdet på $a$ lika med $3$ efter ett anrop till $D(a, b)$, medan $b$ förblir $10$.

Betrakta ett träd med positiva heltalsvikter på noderna, där nodvikten för nod $i$ är $c_i$. Vi definierar en "kedjereduktions"-operation på trädet: $T_{u,v}(a)$. Här är $u$ och $v$ två noder i trädet, och $a$ är en positiv heltalsvariabel. Antag att den enkla vägen från $u$ till $v$ i trädet besöker noderna $x_1, x_2, \dots, x_k$ i ordning (där $k \ge 1$, $x_1 = u$ och $x_k = v$). Operationen $T_{u,v}(a)$ innebär att man utför operationen $D(a, c_{x_i})$ i ordning från $i = 1$ till $k$, det vill säga att man sekventiellt reducerar värdet på variabeln $a$ med hjälp av nodvikterna längs vägen.

Betrakta ett träd $R$ som från början endast innehåller en nod (med nummer $1$ och nodvikt $c_1$). För att låta det växa till ett träd med $n$ noder behöver du utföra $n - 1$ tillväxtoperationer. I den $i$:te operationen ges tre heltal $a_i, u_i, v_i$, där $u_i$ och $v_i$ garanterat är noder som redan finns i det aktuella trädet, och $a_i$ är en positiv heltalsvariabel. Du ska först utföra kedjereduktionsoperationen $T_{u_i,v_i}(a_i)$ och sedan lägga till en ny nod i trädet: denna nya nod får numret $i + 1$, dess vikt $c_{i+1}$ är värdet på $a_i$ efter kedjereduktionen, och den kopplas samman med nod $v_i$.

Slutligen, skriv ut nodvikterna för varje nod som svar.

Indata

Den första raden innehåller två positiva heltal $n$ och $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), vilket representerar att ett träd med $n$ noder ska växa fram, där startvikten för den första noden är $c_1$.

Från den andra till den $n$:te raden innehåller den $i$:te raden tre positiva heltal $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), vilket anger att den $i$:te noden växer fram, kopplas till nod $v_i$, och att dess vikt $c_i$ är resultatet av att utföra operationen $T_{u_i,v_i}(a_i)$ på $a_i$.

Utdata

Skriv ut en rad som innehåller $n$ positiva heltal, åtskilda av mellanslag, som representerar vikterna $c_1, c_2, \dots, c_n$.

Exempel

Indata 1

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

Utdata 1

10 3 2 7 2