لنفترض وجود متغيرين صحيحين موجبين $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