Considérons deux variables entières strictement positives $a$ et $b$. Nous définissons une opération de « réduction » : $D(a, b)$ consiste à remplacer la valeur de la variable $a$ par $\frac{a}{\gcd(a,b)}$, tandis que la valeur de $b$ reste inchangée. Ici, $\gcd(a, b)$ désigne le plus grand commun diviseur de $a$ et $b$. Par exemple, si $a = 6$ et $b = 10$, alors après un appel à $D(a, b)$, la valeur de $a$ devient $3$, tandis que $b$ reste égale à $10$.

Considérons un arbre dont les poids des sommets sont des entiers strictement positifs, où le poids du sommet $i$ est $c_i$. Nous définissons une opération de « réduction sur chaîne » sur l'arbre : $T_{u,v}(a)$. Ici, $u$ et $v$ sont deux sommets de l'arbre, et $a$ est une variable entière strictement positive. Supposons que le chemin simple de $u$ à $v$ dans l'arbre passe successivement par les sommets $x_1, x_2, \dots, x_k$ (où $k \ge 1$, $x_1 = u$ et $x_k = v$). L'opération $T_{u,v}(a)$ consiste à effectuer l'opération $D(a, c_{x_i})$ dans l'ordre de $i = 1$ à $k$, c'est-à-dire à réduire séquentiellement la valeur de la variable $a$ selon l'ordre des poids des sommets le long du chemin.

Considérons un arbre $R$ qui ne contient initialement qu'un seul sommet (numéroté $1$, de poids $c_1$). Pour le faire croître jusqu'à obtenir un arbre à $n$ sommets, vous devez effectuer $n - 1$ opérations de croissance. Lors de la $i$-ème opération, trois entiers $a_i, u_i, v_i$ sont donnés, où $u_i$ et $v_i$ sont garantis d'être des sommets déjà présents dans l'arbre actuel, et $a_i$ est une variable entière strictement positive. Vous devez d'abord effectuer l'opération de réduction sur chaîne $T_{u_i,v_i}(a_i)$, puis ajouter un nouveau sommet à l'arbre : ce nouveau sommet porte le numéro $i + 1$, son poids $c_{i+1}$ est la valeur de $a_i$ après la réduction sur chaîne, et il est relié au sommet $v_i$.

Enfin, veuillez afficher le poids de chaque sommet comme réponse.

Entrée

La première ligne contient deux entiers strictement positifs $n$ et $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), indiquant qu'il faut faire croître un arbre à $n$ sommets, où le poids initial du premier sommet est $c_1$.

De la deuxième ligne à la $n$-ième ligne, la $i$-ème ligne contient trois entiers strictement positifs $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), indiquant la croissance du $i$-ème sommet, qui est relié au sommet $v_i$, et dont le poids $c_i$ est le résultat de l'opération $T_{u_i,v_i}(a_i)$ appliquée à $a_i$.

Sortie

Affichez une ligne contenant $n$ entiers strictement positifs séparés par des espaces, représentant les poids $c_1, c_2, \dots, c_n$.

Exemple

Entrée 1

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

Sortie 1

10 3 2 7 2