Pentru mulţimea {1, 2, 3, ..., n} vom construi toate submulţimile care au proprietatea că în orice submulţime nu există două numere consecutive. De exemplu, pentru mulţimea {1, 2, 3}, submulţimile care îndeplinesc condiţia sunt {1}, {2}, {3}, {1, 3}. Aceste submulţimi le ordonăm lexicografic. Pentru exemplul anterior, submulţimile ordonate lexicografic sunt: {1}, {1, 3}, {2}, {3}. Aceste submulţimi le numerotăm cu numere naturale începând cu 1. Deci submulţimea {1} are numărul de ordine 1, {1, 3} are numărul de ordine 2 ş.a.m.d.

Cerinţă

Scrieţi un program care să determine submulţimea corespunzătoare unui anumit număr de ordine.

Date de intrare

Fişierul de intrare subm.in conţine pe prima linie numărul natural n. Pe linia a doua se găseşte un număr natural T reprezentând numărul de teste. Pe linia a treia se găsesc, separate prin câte un spaţiu, T numere k₁, k₂, ..., k_T , unde k_i reprezintă un număr de ordine.

Date de ieşire

Fişierul de ieşire subm.out va conţine T linii. Pe linia i (1 <= i <= T) se va scrie submulţimea cu numărul de ordine k_i. Elementele submulţimii sunt scrise în ordine crescătoare, separate prin câte un spaţiu.

Restricţii

• 3 <= n <= 44
• 0 < T <= 1000

Exemplu

subm.in	subm.out
3 4 2 3 1 4	1 3 2 1 3

prof. Dan Pracsiu

Grupul Şcolar "Ştefan Procopiu" Vaslui

dpracsiu@yahoo.com