พิจารณาตัวแปรจำนวนเต็มบวกสองตัวคือ $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)$ หมายถึงการดำเนินการ $D(a, c_{x_i})$ ตามลำดับตั้งแต่ $i = 1$ ถึง $k$ กล่าวคือการลดทอนค่าของตัวแปร $a$ ตามลำดับของน้ำหนักปมบนเส้นทาง

พิจารณาต้นไม้ $R$ ที่เริ่มต้นมีเพียงปมเดียว (หมายเลข $1$ มีน้ำหนักปมเป็น $c_1$) เพื่อที่จะทำให้มันเติบโตเป็นต้นไม้ที่มี $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$ เป็นผลลัพธ์จากการดำเนินการ $T_{u_i,v_i}(a_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