Glītie žogi

Uzdevums

Ričards tikko ir pabeidzis savas jaunās mājas celtniecību. Vienīgais, kas vēl pietrūkst, ir glīts žogs. Tā kā Ričards nejūtas liels speciālists žogu izgatavošanā, viņš ir nolēmis tos pasūtīt. Kādas firmas katalogā Ričards ir atradis glītu žogu izgatavošanas aprakstu līdz ar gatavu paraugu attēliem.

Katrs žogs sastāv no N koka dēlīšiem, kas salikti vertikāli viens blakus otram.
Žogs izskatās glīti, ja vienlaicīgi ir izpildīti sekojoši nosacījumi:

• Dēlīšiem ir atšķirīgi garumi - tie ir tieši 1,2,...,N vienības gari;
• Katrs no dēlīšiem ir vai nu garāks par abiem tā kaimiņiem, vai arī īsāks par tiem.

No glīto žogu apraksta seko, ka katru N dēlīšu žogu var aprakstīt kā skaitļu 1,2,...,N permutāciju a₁,a₂,...,a_N, tādu, ka visiem i,1<i<N ir spēkā sakarība (a_i-a_i-1)*(a_i-a_i+1)>0 un otrādi, katra šāda permutācija aprasta glītu žogu.

Ir acīmredzami, ka no N dēlīšiem var uzbūvēt daudz dažādus glītus žogus. Firmas katalogā ir uzrādīti visi glītie N dēlīšu žogi un tie ir sanumurēti pēc kārtas, sākot ar 1, izmantojot sekojošu sakarību: žogs A (ko apzīmē permutācija a₁,a₂,...,a_N) katalogā ir uzrādīts pirms žoga B (ko apzīmē permutācija b₁,b₂,...,b_N), tad un tikai tad, ja eksistē tāds skaitlis i, ka visiem j<i a_j=b_j un a_i<b_i.

Pēc rūpīgas glīto žogu izpētes, Ričards ir nolēmis nopirkt dažus no tiem un uzrakstījis attiecīgo žogu dēlīšu skaitu un kataloga numurus uz lapiņas. Diemžēl ir izrādījies, ka laika gaitā firmas katalogs kaut kur ir noklīdis un palikusi vien Ričarda rakstītā lapiņa. Jūsu uzdevums ir uzrakstīt programmu, kas pēc šīs informācijas atjauno glītā žoga izskatu.

Ievaddati

Teksta faila fence.in pirmā rinda satur naturālu skaitli K(1<=K<=100) - glīto žogu skaitu.

Tālāk seko K datu rindas, katra no kurām apraksta vienu glīto žogu un satur divus naturālus skaitļus - žoga dēlīšu skaitu N(1<=N<=20) un žoga kārtas numuru katalogā C. Starp šiem skaitļiem ievaddatos ir viens tukšumsimbols.
Jūs varat pieņemt, ka glīto žogu skaits ar 20 dēlīšiem ietilpst 64 bitu vesela tipa mainīgajā. Tāpat ir zināms, ka C ir vismaz 1 un nepārsniedz katalogā esošo N dēlīšu glīto žogu skaitu.

Izvaddati

Teksta failam fence.out jāsatur tieši K rindas. Katrā rindā jāizvada viena glītā žoga apraksts. Faila i-tajā rindā jāizvada tā glītā žoga izskats, kas atbilst ievaddatu i+1-ajā datu rindā aprakstītajam - tas ir glīts N dēlīšu žogs, kurš katalogā ir ar kārtas numuru C. Ja glīto žogu apraksta permutācija a₁,a₂,...,a_N, tad šajā rindā jāizvada skaitļi a_i pareizā secībā. Starp katriem diviem blakus skaitļiem izvaddatos jābūt vienam tukšumsimbolam.

Piemērs

fence.in	fence.out
2 2 1 3 3	1 2 2 3 1

Atsauces