Yana, Mino, White ו-Huzz הם החברים הכי טובים.

יום אחד ביקש המאמן מ-White, מ-Mino ומ-Huzz להכין תחרות אימון. Huzz תכנן בעיית חיפוש יפהפייה שהסיבוכיות שלה מעריכית ביחס ל-$k$. הוא בדק בקפידה את כל נוסח הבעיה, פרט לפרט אחד: הוא כתב בטעות $k \le 5 \times 10^5$ במקום $k \le 10$. מאוחר יותר הופיעה בעיה זו בתחרות האימון. המתחרה הזועמת, Yana, ניגשה אל Huzz ושאלה כיצד אמורים לפתור את הבעיה. אך נראה שהוא שכח משהו, ונוסח הבעיה שהוא הציג נראה מעט שונה —

נתון לך גרף מכוון עם $n$ צמתים ו-$m$ קשתות, שבו לכל קשת $e$ מוקצה משקל שלם $w(e)$ בין $1$ ל-$8$.

מסלול הוא סדרה של קשתות $(e_1, e_2, \dots, e_\ell)$ כך שנקודת הקצה של $e_i$ היא נקודת ההתחלה של $e_{i+1}$ לכל $1 \le i < \ell$. אורך המסלול הוא $\ell$, מספר הקשתות שהוא מכיל. שים לב שמסלול עשוי להכיל את אותה קשת מספר פעמים.

סדרת המשקלים של המסלול היא סדרת משקלי הקשתות $[w(e_1), w(e_2), \dots, w(e_\ell)]$. מסלולים מושווים לפי הסדר הלקסיקוגרפי של סדרות המשקלים שלהם.

שני מסלולים נחשבים שונים כל עוד הם משתמשים בקשתות שונות, גם אם הם חולקים את אותה סדרת צמתים ואותה סדרת משקלים. לדוגמה, אם לשני המסלולים $(e_1, e_2)$ ו-$(e_3, e_4)$ יש סדרת משקלים [1,2], ושניהם עוברים בצמתים $1 \to 2 \to 3$, הם עדיין שונים כל עוד $e_1 \neq e_3$ או $e_2 \neq e_4$.

White רוצה למצוא את $k$ המסלולים הקטנים ביותר לקסיקוגרפית. מאחר שהפלט הכולל עלול להיות גדול מדי, עליך להדפיס רק את האורך של כל מסלול.

קלט

השורה הראשונה של הקלט מכילה שלושה מספרים שלמים $n, m, k$ ($2 \le n \le 5 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le k \le 5 \times 10^5$), המייצגים את מספר הצמתים, מספר הקשתות ומספר המסלולים הנדרש.

כל אחת מ-$m$ השורות הבאות מכילה שלושה מספרים שלמים $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), המייצגים קשת מכוונת $e = (x, y)$ עם משקל $w(e) = z$. קבוצת הקשתות הנתונה עשויה להכיל קשתות מרובות.

פלט

הדפס $k$ שורות. השורה ה-$i$ צריכה להכיל מספר שלם יחיד, אורך המסלול שמשקלו הוא ה-$i$ הקטן ביותר בסדר לקסיקוגרפי. אם יש פחות מ-$i$ מסלולים, הדפס $-1$ במקום זאת.

דוגמאות

קלט

5 5 8
2 1 1
3 1 2
4 1 1
1 5 2
5 2 1

פלט

1
1
1
2
3
4
5
6

קלט

3 4 10
1 2 1
1 2 1
2 3 2
2 3 3

פלט

1
1
2
2
2
2
1
1
-1
-1

קלט

6 5 15
1 2 3
2 3 5
3 4 2
3 5 1
5 6 4

פלט

1
2
1
1
2
3
4
3
1
1
2
3
2
-1
-1

הערה

לשם פשטות, תהי $e_j$ הקשת ה-$j$ בקלט.

עבור מקרה הבדיקה הראשון, $8$ המסלולים הקטנים ביותר לקסיקוגרפית הם:

• מסלול $(e_1)$, סדרת משקלים [1].
• מסלול $(e_3)$, סדרת משקלים [1].
• מסלול $(e_5)$, סדרת משקלים [1].
• מסלול $(e_5, e_1)$, סדרת משקלים [1,1].
• מסלול $(e_5, e_1, e_4)$, סדרת משקלים [1,1,2].
• מסלול $(e_5, e_1, e_4, e_5)$, סדרת משקלים [1,1,2,1].
• מסלול $(e_5, e_1, e_4, e_5, e_1)$, סדרת משקלים [1,1,2,1,1].
• מסלול $(e_5, e_1, e_4, e_5, e_1, e_4)$, סדרת משקלים [1,1,2,1,1,2].