acoperire

Marele Maestru dorește să construiască o tablă de șah specială, cu $8$ linii și $8$ coloane. O acoperire a acestei table este un mod de a aranja pătrate mai mici (nu neapărat toate de aceeași mărime), astfel încât pătratele să nu se suprapună între ele, dar să acopere perfect întreaga suprafață a tablei de șah. Laturile pătratelor pot fi orice număr întreg între $1$ și $8$.

Parcurgând celulele matricei asociate tablei de la stânga la dreapta și de sus în jos (mai întâi pe linii, apoi pe coloane), scriem într-o listă latura pătratelor pe care le parcurgem doar prima oară când le întâlnim. Această listă reprezintă transcrierea acoperirii.

De exemplu, să considerăm următoarea acoperire:

Aici am folosit un pătrat $6 \times 6$ (A), șase pătrate $2 \times 2$ (B, C, D, E, F, G) și patru pătrate $1 \times 1$ (H, I, J, K). Parcurgând tabla, vom obține lista de transcriere:
[6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1].

Dacă, de exemplu, ne uităm la altă operă a Maestrului:

În acest caz, pătratele sunt deja etichetate în ordinea primei lor apariții la parcurgerea tablei. Prin urmare, transcrierea completă a acoperirii este
[1, 1, 2, 2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 2].

Generăm toate listele care corespund unor acoperiri valide ale tablei $8 \times 8$ și le sortăm lexicografic.

Se dau $Q$ cerințe care pot fi de două tipuri:

1. Tipul 1. Dată fiind o listă generată de o acoperire validă, să se determine a câta este această listă ca indice în ordinea lexicografică a tuturor listelor valide (cu indexare de la 1).
2. Tipul 2. Dat fiind un indice $K$, să se determine lista corespunzătoare acoperirii aflate pe poziția $K$ în ordinea lexicografică (cu indexare tot de la 1).

Date de intrare

Pe prima linie se va afla un singur număr întreg $Q$, reprezentând numărul de cerințe.
Pe următoarele $Q$ linii se vor afla cerințele, având unul dintre următoarele două formate:

• $1$ $L$ $x_1$ $x_2$ $\dots$ $x_L$: o cerință de tipul 2. Primul număr este $1$, urmat de $L$ (lungimea listei), iar apoi de cele $L$ elemente ale listei.
• $2$ $K$: o cerință de tipul 2. Primul număr este $2$, urmat de indicele $K$.

Date de ieșire

Se vor afișa $Q$ linii, reprezentând răspunsurile pentru fiecare cerință, în ordinea din fișierul de intrare:

• Pentru o cerință de tipul 1, se va afișa un singur număr întreg $K$, reprezentând indicele listei în ordinea lexicografică.
• Pentru o cerință de tipul 2, se va afișa lungimea listei $L$, urmată de cele $L$ elemente ale listei separate prin câte un spațiu.

Restricții

• $Q \leq 100 \ 000$
• $1 \leq K \leq 10^{18}$
• Pentru cerințele de tip 1 se garantează că lista dată provine dintr-o acoperire validă.
• Pentru cerințele de tip 2 se garantează că există cel puțin $K$ acoperiri valide.
• Ordinea lexicografică: O listă $A$ de lungime $L_A$ este strict mai mică lexicografic decât o listă $B$ de lungime $L_B$ dacă există o poziție $i$ astfel încât primele $i-1$ elemente sunt identice, iar $A_i < B_i$. Dacă nu există o astfel de poziție, dar $L_A < L_B$ și elementele coincid până la lungimea $L_A$, se consideră de asemenea că $A$ este mai mică lexicografic decât $B$.
• Deoarece trebuie citite multe numere, vă recomandăm folosirea std::ios_base::sync_with_stdio(false); std::cin.tie(0); ca primă linie în funcția main() , pentru a face citirea mai rapidă

Exemplu

stdin

2
2 2
1 64 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

stdout

61 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1
1

Explicație

Pentru prima cerință, ni se cere lista corespunzătoare acoperirii aflate pe poziția $2$ în ordinea lexicografică.
Prima acoperire posibilă (cea mai mică lexicografic, de pe poziția $1$) este formată exclusiv din 64 de pătrate $1 \times 1$.
Următoarea acoperire în ordine lexicografică este cea în care avem un singur pătrat $2 \times 2$, iar pentru a păstra elementele de $1$ cât mai mult timp la începutul listei, acest pătrat $2 \times 2$ trebuie plasat cât mai târziu posibil pe tablă. Această poziție optimă este chiar colțul din dreapta-jos (ocupând intersecția ultimelor două linii cu ultimele două coloane).

Când parcurgem și transcriem această tablă:

• Trecem prin primele 6 linii complet și prin primele 6 celule din linia 7: adăugăm la listă 54 de valori de $1$.
• Ajungem la pătratul de $2 \times 2$ pe care abia acum îl întâlnim: adăugăm la listă o valoare de 2. (Următoarea celulă din rând este deja acoperită de acest pătrat, deci o sărim).
• Trecem pe ultima linie. Primele 6 celule sunt libere: adăugăm încă 6 valori de $1$. (Ultimele două celule sunt deja acoperite de pătratul $2 \times 2$).

Astfel, obținem o listă de lungime $61$, formată din $54$ de $1$, urmată de un $2$, apoi de încă șase valori de $1$.

Pentru a doua cerință, se dă lista formată din $64$ de elemente egale cu $1$ și se cere poziția sa. Așa cum am dedus și anterior, aceasta este absolut prima acoperire din ordinea lexicografică, așadar răspunsul este $1$.