Рассмотрим две положительные целочисленные переменные $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