permutare

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$:
poziție permutare

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\ \dots\ a_{2n}$ și se compune din valorile
2 – tipul întrebării,
n – ordinul permutării,
$a_1\ a_2\ \dots\ 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 permutare.in conține pe fiecare linie câte o întrebare de orice tip.

Date de ieșire

Fișierul permutare.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.
• problema va fi evaluată pe teste în valoare de 90 de puncte.
• se vor acorda 10 puncte din oficiu.

Exemplu

permutare.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	

permutare.out

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

Explicații

• A doua permutare de ordin 3 (1,2,4,3,5,6)
• Permutarea (1,3,5,2,4,6) are poziția 5
• Prima permutare de ordin 4 (1,2,3,4,5,6,7,8)
• Permutarea (1,2,3,4,5,6,7,8) are poziția 1