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