Definim o permutare dublă de ordin n ca fiind un șir format din primele 2n numere naturale nenule: (a[1], a[2], ... , a[n], a[n+1], a[n+2], ... , a[2n]). Această permutare dublă este de trei ori în creștere, dacă sunt adevărate următoarele trei proprietăți:

1. secvența formată din primele n elemente este crescătoare: a[1]<a[2]< ... < a[n]
2. secvența formată din ultimele n elemente este crescătoare: a[n+1]<a[n+2]< ... < a[2n]
3. perechile ordonate formate din elementele aflate pe poziții identice ale celor două secvențe sunt de asemenea în ordine crescătoare: a[1]<a[n+1], a[2]<a[n+2], ... , a[n]<a[2n].

De exemplu permutarea (1,3,4,2,5,6) este o permutare dublă de ordin 3, de trei ori în creștere, pentru că secvențele (1,3,4) și (2,5,6) formează șiruri crescătoare, iar toate perechile formate din elementele de pe poziții identice: (1,2), (3,5), (4,6) formează de asemenea șiruri crescătoare.

Următoarele permutări duble nu au proprietatea de trei ori în creștere:

• (1,4,3,2,5,6) – secvența (1,4,3) nu este crescătoare,
• (1,3,4,2,6,5) – secvența (2,6,5) nu este crescătoare,
• (1,4,5,2,3,6) – perechea (4,3) nu este crescătoare.

Pentru simplificare în continuare permutarea dublă de trei ori în creștere se va numi permutare.

Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1. Tabelul de mai jos conține datele pentru n=3:

Există două tipuri de întrebări:

1. Ce permutare se află pe o poziție dată?
2. Pe ce poziție se află o permutare dată?

Prima întrebare este codificată astfel: 1 n p și se compune din valorile: 1 – tipul întrebării, n – ordinul permutării, p – poziția permutării cerute.

A doua întrebare este codificată astfel: 2 n a[1] a[2] ... a[2n] și se compune din valorile: 2 – tipul întrebării, n – ordinul permutării, a[1] a[2] ... a[2n] – elementele permutării.

Exemple:

Întrebarea 1 3 2 înseamnă: “Ce permutare de ordin 3 se află pe poziția 2 în ordine lexicografică?” și are răspunsul: 1 2 4 3 5 6.
Întrebarea 2 3 1 3 5 2 4 6 înseamnă: “Pe ce poziție se află permutarea de ordin 3: 1 3 5 2 4 6?” și are răspunsul: 5.

Cerința

Să se răspundă corect la un set de întrebări.

Date de intrare

Fișierul de intrare permutare2.in conține pe fiecare linie câte o întrebare de orice tip.

Date de ieșire

Fișierul de ieșire permutare2.out va conține pe câte o linie câte un răspuns la fiecare întrebare din fișierul de intrare, în ordinea întrebărilor.

Restricții și precizări

• 2 < n < 1 000;
• 0 < p <= 1 000 000 000 (în cazul întrebărilor de tip 1);
• răspunsul la întrebările de tip 2 este <= 1 000 000 000;
• fișierele de intrare vor conține cel mult 2000 de întrebări;
• pentru teste în valoare de 20 de puncte numărul de întrebări va fi 1000 iar numerele de ordine ce intervin în calcule vor fi mai mici decât 5000;
• pentru teste în valoare de 30 de puncte întrebările vor fi de tipul 1;
• pentru teste în valoare de 30 de puncte întrebările vor fi de tipul 2;
• pentru teste în valoare de 30 de puncte întrebările vor fi mixte.
• În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplu

permutare2.in

1 3 2
2 3 1 3 5 2 4 6
1 4 1
2 4 1 2 3 4 5 6 7 8

permutare2.out

1 2 4 3 5 6
5
1 2 3 4 5 6 7 8
1