Considere dos variables enteras positivas $a$ y $b$. Definimos una operación de "reducción": $D(a, b)$ significa cambiar el valor de la variable $a$ a $\frac{a}{\gcd(a,b)}$, mientras que el valor de $b$ permanece sin cambios. Aquí, $\gcd(a, b)$ denota el máximo común divisor de $a$ y $b$. Por ejemplo, si $a = 6$ y $b = 10$, después de llamar a $D(a, b)$ una vez, el valor de $a$ pasa a ser $3$, mientras que $b$ sigue siendo $10$.

Considere un árbol con pesos en los vértices que son enteros positivos, donde el peso del nodo $i$ es $c_i$. Definimos una operación de "reducción en cadena" en el árbol: $T_{u,v}(a)$. Aquí, $u$ y $v$ son dos nodos del árbol, y $a$ es una variable entera positiva. Supongamos que el camino simple de $u$ a $v$ en el árbol visita en orden los nodos $x_1, x_2, \dots, x_k$ (donde $k \ge 1$, $x_1 = u$ y $x_k = v$). La operación $T_{u,v}(a)$ significa realizar la operación $D(a, c_{x_i})$ en orden desde $i = 1$ hasta $k$, es decir, reducir secuencialmente el valor de la variable $a$ usando los pesos de los vértices a lo largo del camino.

Considere un árbol $R$ que inicialmente solo contiene un nodo (etiquetado con $1$ y con peso $c_1$). Para hacerlo crecer hasta convertirse en un árbol con $n$ nodos, debe realizar $n - 1$ operaciones de crecimiento. En la $i$-ésima operación, se dan tres enteros $a_i, u_i, v_i$, donde se garantiza que $u_i$ y $v_i$ son nodos actualmente presentes en el árbol, y $a_i$ es una variable entera positiva. Primero debe realizar la operación de reducción en cadena $T_{u_i,v_i}(a_i)$, y luego agregar un nuevo nodo al árbol: este nuevo nodo tiene la etiqueta $i + 1$, su peso $c_{i+1}$ es el valor de $a_i$ después de la reducción en cadena, y está conectado al nodo $v_i$.

Finalmente, imprima los pesos de cada nodo como respuesta.

Entrada

La primera línea contiene dos enteros positivos $n$ y $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), que representan la necesidad de hacer crecer un árbol con $n$ nodos, donde el peso inicial del primer nodo es $c_1$.

Desde la segunda línea hasta la $n$-ésima línea, la $i$-ésima línea contiene tres enteros positivos $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), lo que indica que crece el $i$-ésimo nodo, conectado al nodo $v_i$, y su peso $c_i$ es el resultado de realizar la operación $T_{u_i,v_i}(a_i)$ sobre $a_i$.

Salida

Imprima una línea con $n$ enteros positivos separados por espacios, que representan los pesos $c_1, c_2, \dots, c_n$.

Ejemplo

Entrada 1

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

Salida 1

10 3 2 7 2