Xét hai biến nguyên dương $a$ và $b$. Chúng ta định nghĩa một thao tác "rút gọn": $D(a, b)$ nghĩa là thay đổi giá trị của biến $a$ thành $\frac{a}{\gcd(a,b)}$, trong khi giá trị của $b$ giữ nguyên. Ở đây $\gcd(a, b)$ biểu thị ước chung lớn nhất của $a$ và $b$. Ví dụ, nếu $a = 6$ và $b = 10$, thì sau khi gọi $D(a, b)$ một lần, giá trị của $a$ trở thành $3$, trong khi $b$ vẫn là $10$.

Xét một cây có trọng số đỉnh đều là các số nguyên dương, trong đó trọng số đỉnh của nút $i$ là $c_i$. Chúng ta định nghĩa một thao tác "rút gọn trên đường đi" trên cây: $T_{u,v}(a)$. Ở đây $u$ và $v$ là hai nút trong cây, và $a$ là một biến nguyên dương. Giả sử đường đi đơn từ $u$ đến $v$ trong cây lần lượt đi qua các nút $x_1, x_2, \dots, x_k$ (trong đó $k \ge 1$, $x_1 = u$ và $x_k = v$). Thao tác $T_{u,v}(a)$ nghĩa là lần lượt thực hiện thao tác $D(a, c_{x_i})$ theo thứ tự từ $i = 1$ đến $k$, tức là rút gọn tuần tự giá trị của biến $a$ theo thứ tự trọng số đỉnh trên đường đi.

Xét một cây $R$ ban đầu chỉ chứa một nút duy nhất (được đánh số $1$, có trọng số đỉnh là $c_1$). Để phát triển nó thành một cây gồm $n$ nút, bạn cần thực hiện $n - 1$ thao tác phát triển. Ở thao tác thứ $i$, ba số nguyên $a_i, u_i, v_i$ được cho, trong đó $u_i$ và $v_i$ được đảm bảo là các nút hiện có trong cây, và $a_i$ là một biến nguyên dương. Trước tiên bạn cần thực hiện thao tác rút gọn trên đường đi $T_{u_i,v_i}(a_i)$, sau đó thêm một nút mới vào cây: nút mới này có số hiệu là $i + 1$, trọng số đỉnh $c_{i+1}$ của nó là giá trị của $a_i$ sau khi rút gọn trên đường đi, và nút này được nối với nút $v_i$.

Cuối cùng, hãy in ra trọng số đỉnh của mỗi nút làm câu trả lời.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n$ và $c_1$ ($1 \le n \le 2 \times 10^5$, $1 \le c_1 \le 10^6$), biểu thị việc cần phát triển một cây gồm $n$ nút, trong đó trọng số ban đầu của nút đầu tiên là $c_1$.

Từ dòng thứ hai đến dòng thứ $n$, dòng thứ $i$ chứa ba số nguyên dương $a_i, u_i, v_i$ ($1 \le u_i, v_i < i$, $1 \le a_i \le 10^6$), biểu thị việc phát triển nút thứ $i$, nút này được nối với nút $v_i$, và trọng số $c_i$ của nó là kết quả sau khi thực hiện thao tác $T_{u_i,v_i}(a_i)$ trên $a_i$.

Kết quả

In ra một dòng gồm $n$ số nguyên dương, cách nhau bởi dấu cách, biểu thị các trọng số $c_1, c_2, \dots, c_n$.

Ví dụ

Dữ liệu vào 1

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

Kết quả 1

10 3 2 7 2