Consideriamo due variabili intere positive $a$ e $b$. Definiamo un'operazione di "riduzione": $D(a, b)$ significa modificare il valore della variabile $a$ in $\frac{a}{\gcd(a,b)}$, mentre il valore di $b$ rimane invariato. Qui, $\gcd(a, b)$ indica il massimo comun divisore di $a$ e $b$. Ad esempio, se $a = 6$ e $b = 10$, dopo aver chiamato $D(a, b)$ una volta, il valore di $a$ diventa $3$, mentre $b$ rimane $10$.

Consideriamo un albero con pesi dei vertici interi positivi, dove il peso del nodo $i$ è $c_i$. Definiamo sull'albero un'operazione di "riduzione su catena": $T_{u,v}(a)$. Qui, $u$ e $v$ sono due nodi dell'albero e $a$ è una variabile intera positiva. Supponiamo che il cammino semplice da $u$ a $v$ nell'albero visiti nell'ordine i nodi $x_1, x_2, \dots, x_k$ (dove $k \ge 1$, $x_1 = u$ e $x_k = v$). L'operazione $T_{u,v}(a)$ consiste nell'eseguire in ordine da $i = 1$ a $k$ l'operazione $D(a, c_{x_i})$, ovvero ridurre in sequenza il valore della variabile $a$ usando i pesi dei vertici lungo il cammino.

Consideriamo un albero $R$ che inizialmente contiene un solo nodo (etichettato con $1$, con peso $c_1$). Per farlo crescere fino a diventare un albero con $n$ nodi, devi eseguire $n - 1$ operazioni di crescita. Nella $i$-esima operazione vengono forniti tre interi $a_i, u_i, v_i$, dove è garantito che $u_i$ e $v_i$ siano nodi già presenti nell'albero corrente, e $a_i$ è una variabile intera positiva. Devi prima eseguire l'operazione di riduzione su catena $T_{u_i,v_i}(a_i)$, e poi aggiungere un nuovo nodo all'albero: questo nuovo nodo ha etichetta $i + 1$, il suo peso $c_{i+1}$ è il valore di $a_i$ dopo la riduzione su catena, ed è collegato al nodo $v_i$.

Infine, stampa i pesi di ciascun nodo come risposta.

Input

La prima riga contiene due interi positivi $n$ e $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), che indicano la necessità di far crescere un albero con $n$ nodi, dove il peso iniziale del primo nodo è $c_1$.

Dalla seconda alla $n$-esima riga, la $i$-esima riga contiene tre interi positivi $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), ad indicare che viene fatto crescere l'$i$-esimo nodo, collegato al nodo $v_i$, e il cui peso $c_i$ è il risultato dell'esecuzione dell'operazione $T_{u_i,v_i}(a_i)$ su $a_i$.

Output

Stampa una riga contenente $n$ interi positivi separati da spazi, che rappresentano i pesi $c_1, c_2, \dots, c_n$.

Esempio

Input 1

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

Output 1

10 3 2 7 2