Розглянемо дві додатні цілочисельні змінні $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)$ означає послідовне виконання операцій $D(a, c_{x_i})$ від $i = 1$ до $k$, тобто почергове скорочення значення змінної $a$ за порядком ваг вершин уздовж шляху.

Розглянемо дерево $R$, яке спочатку містить лише одну вершину (з номером $1$ і вагою $c_1$). Щоб виростити з нього дерево з $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$ якої є результатом застосування операції $T_{u_i,v_i}(a_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