Tinjau dua variabel bilangan bulat positif $a$ dan $b$. Kita mendefinisikan operasi "reduksi": $D(a, b)$ berarti mengubah nilai variabel $a$ menjadi $\frac{a}{\gcd(a,b)}$, sedangkan nilai $b$ tetap tidak berubah. Di sini, $\gcd(a, b)$ menyatakan faktor persekutuan terbesar dari $a$ dan $b$. Sebagai contoh, jika $a = 6$ dan $b = 10$, maka setelah memanggil $D(a, b)$ satu kali, nilai $a$ menjadi $3$, sedangkan $b$ tetap $10$.

Tinjau sebuah pohon dengan bobot simpul berupa bilangan bulat positif, di mana bobot simpul dari simpul $i$ adalah $c_i$. Kita mendefinisikan operasi "reduksi rantai" pada pohon: $T_{u,v}(a)$. Di sini, $u$ dan $v$ adalah dua simpul di dalam pohon, dan $a$ adalah variabel bilangan bulat positif. Misalkan jalur sederhana dari $u$ ke $v$ di dalam pohon mengunjungi simpul-simpul $x_1, x_2, \dots, x_k$ secara berurutan (dengan $k \ge 1$, $x_1 = u$, dan $x_k = v$). Operasi $T_{u,v}(a)$ berarti melakukan operasi $D(a, c_{x_i})$ secara berurutan dari $i = 1$ hingga $k$, yaitu mereduksi nilai variabel $a$ secara berurutan menggunakan bobot simpul di sepanjang jalur tersebut.

Tinjau sebuah pohon $R$ yang awalnya hanya memiliki satu simpul (berlabel $1$, dengan bobot simpul $c_1$). Untuk menumbuhkannya menjadi pohon dengan $n$ simpul, Anda perlu melakukan $n - 1$ operasi pertumbuhan. Pada operasi ke-$i$, diberikan tiga bilangan bulat $a_i, u_i, v_i$, di mana $u_i$ dan $v_i$ dijamin merupakan simpul yang saat ini sudah ada di dalam pohon, dan $a_i$ adalah variabel bilangan bulat positif. Anda harus terlebih dahulu melakukan operasi reduksi rantai $T_{u_i,v_i}(a_i)$, lalu menambahkan sebuah simpul baru ke dalam pohon: simpul baru ini diberi label $i + 1$, bobotnya $c_{i+1}$ adalah nilai $a_i$ setelah reduksi rantai, dan simpul ini dihubungkan ke simpul $v_i$.

Terakhir, keluarkan bobot simpul dari setiap simpul sebagai jawabannya.

Masukan

Baris pertama berisi dua bilangan bulat positif $n$ dan $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), yang menyatakan bahwa kita perlu menumbuhkan pohon dengan $n$ simpul, di mana bobot awal dari simpul pertama adalah $c_1$.

Dari baris kedua hingga baris ke-$n$, baris ke-$i$ berisi tiga bilangan bulat positif $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), yang menyatakan bahwa simpul ke-$i$ ditumbuhkan, dihubungkan ke simpul $v_i$, dan bobotnya $c_i$ adalah hasil dari melakukan operasi $T_{u_i,v_i}(a_i)$ pada $a_i$.

Keluaran

Keluarkan satu baris yang berisi $n$ bilangan bulat positif yang dipisahkan oleh spasi, yang menyatakan bobot $c_1, c_2, \dots, c_n$.

Contoh

Masukan 1

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

Keluaran 1

10 3 2 7 2