order

Se consideră toate șirurile finite de numere naturale nenule ordonate astfel:
[1]; [1,1]; [2]; [1,1,1]; [1,2]; [2,1]; [3]; [1,1,1,1]; [1,1,2]; [1,2,1]; [1,3]; ...

Ordonarea se face după următoarea regulă: dacă avem două șiruri cu sumele termenilor diferite, atunci șirul cu suma termenilor mai mică se găsește pe o poziție mai mică. Dacă avem două șiruri cu sumele termenilor egale atunci se compară termen cu termen șirurile până când se găsește un termen diferit. Șirul care are termenul mai mic se găsește pe poziție mai mică. Cu alte cuvinte, primul criteriu de ordonare este suma termenilor, iar în caz de egalitate, al doilea criteriu de sortare este ordinea lexicografică.

Oricărui șir i se asociază o poziție (număr natural nenul) și invers, oricărei poziții i se asociază un șir.

De exemplu:

• Șirului [1,1,2] i se asociază poziția 9.
• Poziției 14 i se asociază șirul [3,1]

Cerinţe

Să se răspundă la un număr de interogări de tipul:

1. Cunoscând un șir de numere naturale nenule să se determine poziția asociată șirului.
2. Cunoscând un număr natural reprezentând o poziție asociată unui șir să se determine șirul corespunzător.

Date de intrare

Fișierul de intrare order.in conține pe prima linie un număr natural Q reprezentând numărul de interogări.
Pe următoarele Q linii vor fi descrise interogările.
Dacă interogarea este de tip 1 linia va conține numărul 1, apoi un număr natural N reprezentând numărul de termeni ai șirului urmat de N numere naturale separate prin câte un spațiu reprezentând termenii șirului.
Dacă interogarea este de tip 2 linia va conține numărul 2 urmat de un număr natural nenul P reprezentând poziția șirului solicitat.

Date de ieşire

Fișierul de ieșire order.out va conține Q linii. Pe fiecare linie este descris răspunsul la interogarea corespunzătoare din fișierul de intrare.
Dacă interogarea este de tip 1, pe linia corespunzătoare se va afișa un singur număr P reprezentând poziția șirului descris în interogare.
Dacă interogarea este de tip 2, linia corespunzătoare va conține un număr natural N reprezentând numărul de termeni pentru șirul solicitat, urmat de N numere naturale nenule reprezentând termenii șirului. Numerele de pe aceste linii trebuie sa fie separate prin câte un spațiu.

Restricţii și precizări

• $1 ≤ P ≤ 10^{15}$ (mai precis se asigură ca pentru ambele tipuri de interogări poziția asociată șirului considerat nu depășește $10^{15}$ )
• $1 ≤ Q ≤ 10^5$
• Pentru 40 de puncte testele vor conține doar interogări de tip 1
• Pentru 40 de puncte testele vor conține doar interogări de tip 2
• Pentru 20 de puncte testele vor conține interogări de ambele tipuri

Exemplu:

order.in

2
1 3 1 1 2
2 14

order.out

9
2 3 1

Explicații

Fișierul de intrare conține două interogări. Prima este de tip 1 și cere determinarea poziției șirului [1,1,2] care are lungimea 3. Acest șir este pe poziția a 9-a conform ordinii descrise în enunț. A doua interogare cere determinarea șirului aflat pe poziția 14. Acest șir este șirul [3,1] de lungime 2.