Betrachte zwei positiv ganzzahlige Variablen $a$ und $b$. Wir definieren eine „Reduktions“-Operation: $D(a, b)$ bedeutet, den Wert der Variablen $a$ auf $\frac{a}{\gcd(a,b)}$ zu ändern, während der Wert von $b$ unverändert bleibt. Hierbei bezeichnet $\gcd(a, b)$ den größten gemeinsamen Teiler von $a$ und $b$. Wenn beispielsweise $a = 6$ und $b = 10$ ist, wird der Wert von $a$ nach einem einmaligen Aufruf von $D(a, b)$ zu $3$, während $b$ gleich $10$ bleibt.

Betrachte einen Baum mit positiven ganzzahligen Knotengewichten, wobei das Knotengewicht von Knoten $i$ gleich $c_i$ ist. Wir definieren auf dem Baum eine „Kettenreduktions“-Operation: $T_{u,v}(a)$. Hierbei sind $u$ und $v$ zwei Knoten im Baum und $a$ ist eine positiv ganzzahlige Variable. Angenommen, der einfache Pfad von $u$ nach $v$ im Baum besucht der Reihe nach die Knoten $x_1, x_2, \dots, x_k$ (wobei $k \ge 1$, $x_1 = u$ und $x_k = v$ gilt). Die Operation $T_{u,v}(a)$ bedeutet, nacheinander für $i = 1$ bis $k$ die Operation $D(a, c_{x_i})$ auszuführen, also den Wert der Variablen $a$ schrittweise anhand der Knotengewichte entlang des Pfades zu reduzieren.

Betrachte einen Baum $R$, der anfangs nur einen einzigen Knoten enthält (mit der Nummer $1$ und dem Knotengewicht $c_1$). Um ihn zu einem Baum mit $n$ Knoten heranwachsen zu lassen, musst du $n - 1$ Wachstumsoperationen durchführen. In der $i$-ten Operation werden drei ganze Zahlen $a_i, u_i, v_i$ gegeben, wobei garantiert ist, dass $u_i$ und $v_i$ bereits im aktuellen Baum vorhandene Knoten sind, und $a_i$ eine positiv ganzzahlige Variable ist. Du musst zuerst die Kettenreduktionsoperation $T_{u_i,v_i}(a_i)$ ausführen und anschließend einen neuen Knoten zum Baum hinzufügen: Dieser neue Knoten erhält die Nummer $i + 1$, sein Knotengewicht $c_{i+1}$ ist der Wert von $a_i$ nach der Kettenreduktion, und er wird mit dem Knoten $v_i$ verbunden.

Gib schließlich die Knotengewichte aller Knoten als Antwort aus.

Eingabe

Die erste Zeile enthält zwei positive ganze Zahlen $n$ und $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), was bedeutet, dass ein Baum mit $n$ Knoten wachsen soll, wobei das Anfangsgewicht des ersten Knotens $c_1$ beträgt.

Von der zweiten bis zur $n$-ten Zeile enthält die $i$-te Zeile drei positive ganze Zahlen $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), was bedeutet, dass der $i$-te Knoten wächst, mit dem Knoten $v_i$ verbunden wird und sein Gewicht $c_i$ das Ergebnis der Ausführung der Operation $T_{u_i,v_i}(a_i)$ auf $a_i$ ist.

Ausgabe

Gib eine Zeile mit $n$ durch Leerzeichen getrennten positiven ganzen Zahlen aus, die die Gewichte $c_1, c_2, \dots, c_n$ darstellen.

Beispiel

Eingabe 1

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

Ausgabe 1

10 3 2 7 2