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 k1, k2, ..., kT , unde ki 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 ki.
Elementele submulţimii
sunt scrise în ordine crescătoare, separate prin câte un spaţiu.