考慮兩個正整數變量 $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