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].