Yana, Mino, White және Huzz — ең жақын достар.

Бір күні жаттықтырушы White, Mino және Huzz-ға жаттығу жарысын дайындауды тапсырды. Huzz күрделілігі $k$-ға қатысты экспоненциалды болатын әдемі іздеу есебін құрастырды. Ол бір ғана бөлшектен басқа есептің бүкіл шартын мұқият тексеріп шықты: ол байқаусызда $k \le 10$ орнына $k \le 5 \times 10^5$ деп жазып жіберді. Кейінірек бұл есеп жаттығу жарысында келді. Ашуланған қатысушы Yana Huzz-ға келіп, бұл есепті қалай шығару керек екенін сұрады. Бірақ ол бірдеңені ұмытып қалған сияқты, ал оның ұсынған есеп шарты сәл басқаша көрінді —

Сізге $n$ төбесі және $m$ қабырғасы бар бағытталған граф берілген, мұнда әрбір $e$ қабырғасына $1$-ден $8$-ге дейінгі бүтін $w(e)$ салмағы берілген.

Жол дегеніміз — барлық $1 \le i < \ell$ үшін $e_i$ қабырғасының соңы $e_{i+1}$ қабырғасының басы болатындай $(e_1, e_2, \dots, e_\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$ жолдың әрқайсысында салмағы $w(e) = z$ болатын бағытталған $e = (x, y)$ қабырғасын білдіретін үш бүтін сан $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$) берілген. Берілген қабырғалар жиынында еселі қабырғалар болуы мүмкін.

Шығыс деректер

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