נתבונן בשני משתנים שלמים חיוביים $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