== include(page="template/taskheader" task_id="euro3") ==

După calificarea la campionatul european de fotbal din Franţa, având în vizor N jucători din care trebuie să convoace câţiva în echipa naţională, selecţionerul României a apelat la nişte metode mai puţin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să gasească formula câştigătoare pentru meciul de deschidere cu Franţa. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucatori trebuie sa aibă valoarea exact X şi coeficientul de aroganţă cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componenţa lotului. Coeficientul de aroganţă al unui lot de jucători e definit ca diferenţa dintre valoarea maximă a unui jucător din lot şi valoarea minimă a unui jucător din lot. Se mai ştie că valoarea lotului nu poate depăşi o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulţime nevidă de jucători aleşi dintre cei N. Atenţie, un lot poate fi format şi dintr-un singur jucător.

După calificarea la campionatul european de fotbal din Franţa, având în vizor $N$ jucători din care trebuie să convoace câţiva în echipa naţională, selecţionerul României a apelat la nişte metode mai puţin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să gasească formula câştigătoare pentru meciul de deschidere cu Franţa. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucatori trebuie sa aibă valoarea exact $X$ şi coeficientul de aroganţă cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componenţa lotului. Coeficientul de aroganţă al unui lot de jucători e definit ca diferenţa dintre valoarea maximă a unui jucător din lot şi valoarea minimă a unui jucător din lot. Se mai ştie că valoarea lotului nu poate depăşi o valoare cunoscută $**Vmax**$. Un lot de jucători e definit ca o submulţime nevidă de jucători aleşi dintre cei $N$. Atenţie, un lot poate fi format şi dintr-un singur jucător.

h2. Cerinta

Se dă numărul N de jucători, numărul Vmax definit mai sus şi valoarea fiecărui jucător. Selecţionerul României a găsit formula câştigătoare şi e curios dacă puteţi şi voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflaţi pentru fiecare valoare X din intervalul $**[1,Vmax]**$ coeficientul de aroganţă minim posibil pentru care există cel puţin un lot dintre cei N jucători cu valoare exact X. **Dacă nu se poate obţine nici un lot de valoare exact X, se consideră ca răspuns -1.**

Se dă numărul $N$ de jucători, numărul $Vmax$ definit mai sus şi valoarea fiecărui jucător. Selecţionerul României a găsit formula câştigătoare şi e curios dacă puteţi şi voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflaţi pentru fiecare valoare $X$ din intervalul $**[1,Vmax]**$ coeficientul de aroganţă minim posibil pentru care există cel puţin un lot dintre cei $N$ jucători cu valoare exact $X$. **Dacă nu se poate obţine nici un lot de valoare exact $X$, se consideră ca răspuns $-1$.**

h2. Date de intrare

Fişierul de intrare $euro3.in$ conţine pe prima linie T, reprezentând numărul de teste. În continuare vor urma T teste, fiecare având următoarea structură: pe prima linie dintr-un test se află N şi Vmax, reprezentând numărul total de jucători, respectiv valoarea maximă pe care o poate avea un lot de jucători. A doua linie a testului conţine N numere naturale despărţite prin câte un spaţiu. Ali-lea număr de pe această linie reprezintă valoarea pe care o are al i-lea jucător.

Fişierul de intrare $euro3.in$ conţine pe prima linie $T$, reprezentând numărul de teste. În continuare vor urma $T$ teste, fiecare având următoarea structură: pe prima linie dintr-un test se află $N$ şi $Vmax$, reprezentând numărul total de jucători, respectiv valoarea maximă pe care o poate avea un lot de jucători. A doua linie a testului conţine $N$ numere naturale despărţite prin câte un spaţiu. Al $i$-lea număr de pe această linie reprezintă valoarea pe care o are al $i$-lea jucător.

h2. Date de ieşire

În fişierul de ieşire $euro3.out$ se vor afişa T linii, câte una pentru fiecare test din fişierul de intrare. O linie corespunzătoare unui test conţine Vmax numere (Vmax-ul testului curent), unde cel de-al i-lea număr reprezintă coeficientul de aroganţă minim posibil pentru o submulţime de jucători de valoare exact i. În cazul în care nu există o submulţime de jucători de valoare exact i se afişează -1.

În fişierul de ieşire $euro3.out$ se vor afişa $T$ linii, câte una pentru fiecare test din fişierul de intrare. O linie corespunzătoare unui test conţine $Vmax$ numere, unde cel de-al $i$-lea număr reprezintă coeficientul de aroganţă minim posibil pentru o submulţime de jucători de valoare exact $i$. În cazul în care nu există o submulţime de jucători de valoare exact $i$ se afişează $-1$.

h2. Restricţii si precizari

* $1 ≤ N ≤ 4000$
* $1 ≤ Vmax ≤ 8000$
* $1 ≤ valoare[i] ≤ Vmax$

* Pentru $20%$ din teste $N <= 20$
* Pentru $40%$ din teste $N <= 100$ si $Vmax <= 100$
* Pentru $50%$ din teste $N <= 300$ si $Vmax <= 300$

* Pentru $20%$ din teste $N ≤ 20$
* Pentru $40%$ din teste $N ≤ 100$ si $Vmax ≤ 100$
* Pentru $50%$ din teste $N ≤ 300$ si $Vmax ≤ 300$

h2. Exemplu
table(example). |_. euro3.in |_. euro3.out |
| 2

47

4 7

5 2 3 4
5 15
1 8 2 3 6