Untuk menyambut OSN 2014, Pak Dengklek berencana membuat sebuah hiasan dinding di laboratorium tempat Bidang Informatika dilaksanakan. Hiasan ini cukup sederhana, yakni hanya terdiri atas paku-paku dan untaian tali. Pak Dengklek memiliki N buah paku untuk membuat hiasan ini. Paku-paku ini dinomori secara unik dari 1 sampai dengan N.
Cara membuat hiasan dinding ini adalah sebagai berikut. Mula-mula, Pak Dengklek membariskan paku-paku tersebut dalam sebuah barisan. Lalu, Pak Dengklek memasang paku pertama pada dinding. Untuk setiap paku kedua sampai dengan ke-N secara berurutan, Pak Dengklek melakukan langkah-langkah berikut:
Tinjau paku paling atas pada dinding.
Misalkan X = paku yang sedang ditinjau, dan Y = paku yang ingin dipasang.
a. Jika nomor dari Y < nomor dari X:
(i) Jika X tidak memiliki paku yang terhubung dengan tali di sebelah kiri bawahnya, pasang Y persis di
sebelah kiri bawah X, dan hubungkan keduanya menggunakan tali. Pemasangan paku dianggap selesai.
(ii) Jika X memiliki paku yang terhubung dengan tali di sebelah kiri bawahnya, tinjau paku tersebut dan
kembali ke Langkah 2.
b. Jika nomor dari Y > nomor dari X:
(i) Jika X tidak memiliki paku yang terhubung dengan tali di sebelah kanan bawahnya, pasang Y persis di
sebelah kanan bawah X, dan hubungkan keduanya menggunakan tali. Pemasangan paku dianggap selesai.
(ii) Jika X memiliki paku yang terhubung dengan tali di sebelah kanan bawahnya, tinjau paku tersebut dan
kembali ke Langkah 2.
Sebagai contoh, misalkan Pak Dengklek ingin memasang paku keenam bernomor 8. Berikut adalah ilustrasi langkah-langkah pemasangan paku ini:
Pak Dengklek sudah memiliki sebuah desain hiasan dinding yang dibuat oleh panitia dekorasi. Ia ingin segera memasang paku-paku agar terbentuk hiasan dinding tersebut. Tentu saja, mula-mula ia harus membariskan paku-paku tersebut. Mungkin saja ada lebih dari satu kemungkinan barisan yang menghasilkan hiasan dinding tersebut. Pak Dengklek, sebagai seorang yang senang dengan teka-teki logika, justru penasaran dengan pertanyaan berikut: jika barisan-barisan yang mungkin menghasilkan hiasan dinding tersebut diurutkan dengan urutan leksikografis, barisan apa yang berada pada posisi ke-K?
Catatan: barisan paku A lebih kecil daripada barisan paku B secara leksikografis, apabila pada posisi pertama di mana A dan B berbeda, nomor paku pada posisi tersebut di A lebih kecil daripada nomor paku pada posis tersebut di B.
Bantulah Pak Dengklek menjawab pertanyaan tersebut, agar ia dapat segera memasang paku-paku tersebut!
Format Masukan
Pada awalnya, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:
Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, dan berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:
Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua berisi dua buah bilangan bulat N dan K. N-1 baris berikutnya mendeskripsikan sebuah desain hiasan dinding. Masing-masing baris berisi tiga buah bilangan bulat u, v, dan t:
Apabila t = 0, maka paku bernomor v terhubung dengan tali di sebelah kiri bawah dengan paku bernomor u.
Apabila t = 1, maka paku bernomor v terhubung dengan tali di sebelah kanan bawah dengan paku bernomor u.
Format Keluaran
Sebuah baris berisi barisan N buah bilangan, dipisahkan oleh spasi, yang menyatakan barisan nomor paku, sedemikian sehingga barisan ini merupakan barisan terkecil ke-K secara leksikografis.
Contoh Masukan 1
0..34.6
4 1
2 1 0
2 4 1
4 3 0
Contoh Keluaran 1
2 1 4 3
Contoh Masukan 2
0..3..6
4 3
2 1 0
2 4 1
4 3 0
Contoh Keluaran 2
2 4 3 1
Pada semua subsoal, berlaku:
Masuk untuk menulis jawaban