Fișierul intrare/ieșire	fatkins.in, fatkins.out	Sursă	Baraj Shumen Vianu Juniori 2015
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.05 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Fatkins

Ion s-a apucat să țină dieta Fatkins, o dietă miraculoasă bazată pe bomboane. În fiecare zi timp de Q zile, Ion primește la ușă câte o cutie cu bomboane. În fiecare cutie se află N bomboane și fiecare bomboană este etichetată cu numărul de calorii pe care îl conține. Toate cutiile conțin același set de bomboane. Dar Ion nu are voie să mănânce toate bomboanele! În ziua i, Ion primește un număr K_i. Considerând toate cele 2^N submulțimi de bomboane, ordonate după conținutul caloric, Ion trebuie să mănânce submulțimea cu numărul de ordine K_i.

Dându-se N, Q, conținutul caloric al celor N bomboane și valorile pentru K_i, determinați câte calorii mănâncă Ion în fiecare zi.

Date de intrare

Fișierul de intrare fatkins.in conține

• pe prima linie numerele N și Q;
• pe a doua linie apar numerele naturale pozitive C₁, C₂, ..., C_N, reprezentând numărul de calorii din fiecare bomboană;
• pe următoarele Q linii numerele naturale K₁, K₂, ..., K_Q, câte unul pe linie.

Date de ieșire

În fișierul de ieșire fatkins.out se vor tipări Q numere, câte unul pe linie, reprezentând caloriile consumate de Ion în fiecare zi. Răspunsurile vor avea aceeași ordine cu întrebările.

Restricții

• 1 ≤ N ≤ 100
• 1 ≤ Q ≤ 1.000
• 1 ≤ K_i ≤ min(2^N, 100.000) pentru 1 ≤ i ≤ Q
• C₁ + C₂ + ... + C_N ≤ 1.000.000.000
• Pentru 20% din teste, 1 ≤ N ≤ 16 și 1 ≤ K_i ≤ 10.000
• Pentru alte 30% din teste, 1 ≤ N ≤ 30 și 1 ≤ K_i ≤ 20.000

Exemplu

Explicație

Cele 16 submulțimi sunt, în ordine: