euro

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.

Cerinţă

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 Njucători cu valoare exact X. Dacă nu se poate obține nici un lot de valoare exact X, se consideră ca răspuns -1.

Date de intrare

Fişierul de intrare euro.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 Nnumere 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.

Date de ieşire

În fişierul de ieşire euro.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ă se afișează -1.

Restricţii si precizări

• 1 ≤ T ≤ 2
• 1 ≤ N ≤ 4000
• 1 ≤ Vmax ≤ 8000
• 1 ≤ valoare[i] ≤ Vmax
• Pentru 20% din teste N <= 20
• Pentru 40% din teste N <= 100 și Vmax <= 100
• Pentru 50% din teste N <= 300 și Vmax <= 300

Exemplu

euro.in

2
4 7
5 2 3 4
5 15
1 8 2 3 6

euro.out

-1 0 0 0 0 2 1
0 0 0 2 1 0 5 0	3 5 4 5	6 2 7

Explicaţie

Pentru primul test:

• Nu se poate găsi un lot de valoarea 1, deci răspunsul pentru 1 este 1.
• Se pot obține loturi de valoare 2, 3, 4, 5 dintr-un singur jucător.
• Lotul de valoare 6 se poate obține din jucătorii cu valorile 2 și 4.
• Pentru valoarea 7 există două loturi posibile formate din jucătorii cu valorile 5 2 respectiv 3 4. Cel din urmă lot are coeficientul de aroganță mai mic (adică max(3,4)-min(3,4)=1).