2 つの正の整数変数 $a$ と $b$ を考えます。「簡約」操作を次のように定義します：$D(a, b)$ は、変数 $a$ の値を $\frac{a}{\gcd(a,b)}$ に変更し、$b$ の値はそのままにすることを表します。ここで $\gcd(a, b)$ は $a$ と $b$ の最大公約数を表します。例えば、$a = 6$ かつ $b = 10$ のとき、$D(a, b)$ を 1 回呼び出すと、$a$ の値は $3$ になり、$b$ は $10$ のままとなります。

頂点重みがすべて正の整数である木を考えます。ここで頂点 $i$ の頂点重みは $c_i$ です。木の上で「パス簡約」操作 $T_{u,v}(a)$ を定義します。ここで $u$ と $v$ は木の中の 2 つの頂点であり、$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 つの頂点（番号は $1$、頂点重みは $c_1$）のみを含む木 $R$ を考えます。これを $n$ 個の頂点を含む木に成長させるために、$n - 1$ 回の成長操作を行う必要があります。$i$ 回目の操作では、3 つの整数 $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$ と辺で結ばれます。

最後に、各頂点の頂点重みを答えとして出力してください。

入力

1 行目には 2 つの正の整数 $n$ と $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$) が与えられ、$n$ 個の頂点を含む木を成長させる必要があり、最初の頂点の初期重みが $c_1$ であることを表します。

2 行目から $n$ 行目までのうち、$i$ 行目には 3 つの正の整数 $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$ 個の正の整数を 1 行に出力してください。これらは重み $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