Rozważmy dwie dodatnie zmienne całkowite $a$ oraz $b$. Definiujemy operację „redukcji”: $D(a, b)$ oznacza zmianę wartości zmiennej $a$ na $\frac{a}{\gcd(a,b)}$, podczas gdy wartość $b$ pozostaje bez zmian. Tutaj $\gcd(a, b)$ oznacza największy wspólny dzielnik liczb $a$ i $b$. Na przykład, jeśli $a = 6$ oraz $b = 10$, to po jednokrotnym wywołaniu $D(a, b)$ wartość $a$ staje się równa $3$, natomiast $b$ pozostaje równe $10$.

Rozważmy drzewo o dodatnich całkowitych wagach wierzchołków, gdzie waga wierzchołka $i$ wynosi $c_i$. Na drzewie definiujemy operację „redukcji łańcuchowej”: $T_{u,v}(a)$. Tutaj $u$ oraz $v$ są dwoma wierzchołkami w drzewie, a $a$ jest dodatnią zmienną całkowitą. Załóżmy, że ścieżka prosta z $u$ do $v$ w drzewie odwiedza kolejno wierzchołki $x_1, x_2, \dots, x_k$ (gdzie $k \ge 1$, $x_1 = u$ oraz $x_k = v$). Operacja $T_{u,v}(a)$ oznacza wykonanie po kolei dla $i = 1$ do $k$ operacji $D(a, c_{x_i})$, czyli kolejne redukowanie wartości zmiennej $a$ przy użyciu wag wierzchołków leżących na ścieżce.

Rozważmy drzewo $R$, które początkowo zawiera tylko jeden wierzchołek (o numerze $1$ i wadze $c_1$). Aby rozwinąć je w drzewo o $n$ wierzchołkach, należy wykonać $n - 1$ operacji wzrostu. W $i$-tej operacji podawane są trzy liczby całkowite $a_i, u_i, v_i$, przy czym gwarantowane jest, że $u_i$ oraz $v_i$ są wierzchołkami znajdującymi się aktualnie w drzewie, a $a_i$ jest dodatnią zmienną całkowitą. Należy najpierw wykonać operację redukcji łańcuchowej $T_{u_i,v_i}(a_i)$, a następnie dodać nowy wierzchołek do drzewa: ten nowy wierzchołek otrzymuje numer $i + 1$, jego waga $c_{i+1}$ jest wartością $a_i$ po redukcji łańcuchowej, i jest on połączony krawędzią z wierzchołkiem $v_i$.

Na koniec wypisz wagi poszczególnych wierzchołków jako odpowiedź.

Wejście

Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n$ oraz $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), oznaczające konieczność wyhodowania drzewa o $n$ wierzchołkach, w którym początkowa waga pierwszego wierzchołka wynosi $c_1$.

Od drugiego do $n$-tego wiersza, $i$-ty wiersz zawiera trzy dodatnie liczby całkowite $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), oznaczające wyhodowanie $i$-tego wierzchołka połączonego z wierzchołkiem $v_i$, którego waga $c_i$ jest wynikiem wykonania operacji $T_{u_i,v_i}(a_i)$ na $a_i$.

Wyjście

Wypisz jeden wiersz zawierający $n$ dodatnich liczb całkowitych oddzielonych spacjami, oznaczających wagi $c_1, c_2, \dots, c_n$.

Przykład

Wejście 1

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

Wyjście 1

10 3 2 7 2