Екі оң бүтін санды $a$ және $b$ айнымалыларын қарастырайық. Біз «қысқарту» операциясын былайша анықтаймыз: $D(a, b)$ дегеніміз $a$ айнымалысының мәнін $\frac{a}{\gcd(a,b)}$-ге өзгертуді білдіреді, ал $b$-ның мәні өзгеріссіз қалады. Мұндағы $\gcd(a, b)$ жазуы $a$ мен $b$ сандарының ең үлкен ортақ бөлгішін білдіреді. Мысалы, егер $a = 6$ және $b = 10$ болса, онда $D(a, b)$ операциясын бір рет шақырғаннан кейін $a$-ның мәні $3$-ке тең болады, ал $b$ мәні $10$ күйінде қалады.

Төбелерінің салмақтары оң бүтін сандар болатын ағашты қарастырайық, мұндағы $i$ төбесінің салмағы $c_i$-ге тең. Ағашта «тізбекті қысқарту» операциясын анықтаймыз: $T_{u,v}(a)$. Мұндағы $u$ мен $v$ — ағаштағы екі төбе, ал $a$ — оң бүтін санды айнымалы. Ағаштағы $u$-дан $v$-ға дейінгі қарапайым жол ретімен $x_1, x_2, \dots, x_k$ төбелері арқылы өтеді делік (мұндағы $k \ge 1$, $x_1 = u$ және $x_k = v$). $T_{u,v}(a)$ операциясы $i = 1$-ден $k$-ға дейін ретімен $D(a, c_{x_i})$ операциясын орындауды, яғни жол бойындағы төбе салмақтарының ретімен $a$ айнымалысының мәнін бірізді қысқартуды білдіреді.

Бастапқыда тек бір төбеден (нөмірі $1$, салмағы $c_1$) тұратын $R$ ағашын қарастырайық. Оны $n$ төбесі бар ағашқа дейін өсіру үшін $n - 1$ өсіру операциясын орындау керек. $i$-ші операцияда үш бүтін сан $a_i, u_i, v_i$ беріледі, мұндағы $u_i$ мен $v_i$ ағымдағы ағашта бар төбелер екеніне кепілдік беріледі, ал $a_i$ — оң бүтін санды айнымалы. Сізге алдымен $T_{u_i,v_i}(a_i)$ тізбекті қысқарту операциясын орындап, содан кейін ағашқа жаңа төбе қосу керек: бұл жаңа төбенің нөмірі $i + 1$ болады, оның $c_{i+1}$ салмағы тізбекті қысқартудан кейінгі $a_i$-дің мәніне тең болады және бұл төбе $v_i$ төбесімен жалғанады.

Соңында жауап ретінде әрбір төбенің салмағын шығарыңыз.

Кіріс деректер

Бірінші жолда екі оң бүтін сан $n$ және $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$) берілген, олар $n$ төбесі бар ағашты өсіру керектігін және бірінші төбенің бастапқы салмағы $c_1$ екенін білдіреді.

Екінші жолдан $n$-ші жолға дейін, $i$-ші жолда үш оң бүтін сан $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$) берілген, олар $i$-ші төбенің өсірілетінін, оның $v_i$ төбесімен жалғанатынын және оның $c_i$ салмағы $a_i$-ге $T_{u_i,v_i}(a_i)$ операциясын қолдану нәтижесі екенін білдіреді.

Шығыс деректер

Бос орын арқылы бөлінген $n$ оң бүтін саннан тұратын бір жолды — $c_1, c_2, \dots, c_n$ салмақтарын шығарыңыз.

Мысал

Кіріс деректер 1

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

Шығыс деректер 1

10 3 2 7 2