Nodea Eugen (eugen_nodea) n cuburi numerotate de la 1 la n pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime H ce se pot forma cu cele n cuburi, astfel încât fiecare turn să respecte următoarele condiții:
- orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
- să nu existe două cuburi consecutive de aceeași culoare;
Date de intrare
Fișierul de intrare turn.in conține pe prima linie două numere naturale n și H, iar pe următoarele n linii descrierea cuburilor. Linia i+1 conține descrierea cubului i sub forma: latură culoare.
Date de ieșire
Fișierul de ieșire turn.out va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime H.
Restricții și precizări
1 ≤ n < 151 ≤ H ≤ 501 ≤ latura ≤ 101 ≤ culoare ≤ 5- nu există cuburi identice
- pentru datele de intrare există întotdeauna soluție
Exemplu:
turn.in
5 5 1 1 2 1 1 2 2 2 3 1
turn.out
2 4 1 4 2 3 5 3 1 5 4
Explicație
Primul turn este format din cuburile: 2 (2,1), 4 (2,2), 1 (1,1).
Al doilea turn este format din cuburile: 4 (2,2), 2 (2,1), 3 (1,2)
etc.