두 양의 정수 변수 $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