Consider two positive integer variables $a$ and $b$. We define a "reduction" operation: $D(a, b)$ means changing the value of variable $a$ to $\frac{a}{\gcd(a,b)}$, while the value of $b$ remains unchanged. Here, $\gcd(a, b)$ denotes the greatest common divisor of $a$ and $b$. For example, if $a = 6$ and $b = 10$, then after calling $D(a, b)$ once, the value of $a$ becomes $3$, while $b$ remains $10$.

Consider a tree with positive integer vertex weights, where the vertex weight of node $i$ is $c_i$. We define a "chain reduction" operation on the tree: $T_{u,v}(a)$. Here, $u$ and $v$ are two nodes in the tree, and $a$ is a positive integer variable. Assume that the simple path from $u$ to $v$ in the tree visits the nodes $x_1, x_2, \dots, x_k$ in order (where $k \ge 1$, $x_1 = u$, and $x_k = v$). The operation $T_{u,v}(a)$ means performing the $D(a, c_{x_i})$ operation in order from $i = 1$ to $k$, that is, using the vertex weights along the path to reduce the value of variable $a$ sequentially.

Consider a tree $R$ that initially has only one vertex (labeled $1$, with a vertex weight of $c_1$). To grow it into a tree with $n$ nodes, you need to perform $n - 1$ growth operations. In the $i$-th operation, three integers $a_i, u_i, v_i$ are given, where $u_i$ and $v_i$ are guaranteed to be nodes currently in the tree, and $a_i$ is a positive integer variable. You need to first perform a chain reduction operation $T_{u_i,v_i}(a_i)$, and then add a new node to the tree: this new node is labeled $i + 1$, its weight $c_{i+1}$ is the value of $a_i$ after the chain reduction, and it is connected to node $v_i$.

Finally, please output the vertex weights of each node as the answer.

Input

The first line contains two positive integers $n$ and $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), representing the need to grow a tree with $n$ nodes, where the initial weight of the first node is $c_1$.

From the second to the $n$-th line, the $i$-th line contains three positive integers $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), indicating that the $i$-th node is grown, connected to node $v_i$, and its weight $c_i$ is the result of performing the $T_{u_i,v_i}(a_i)$ operation on $a_i$.

Output

Output one line containing $n$ positive integers, separated by spaces, representing the weights $c_1, c_2, \dots, c_n$.

Example

Sample Input 1

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

Sample Output 1

10 3 2 7 2