考虑两个正整数变量 $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