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ă găsească formula câștigătoare pentru meciul de deschidere cu Franța. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucători 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ța

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.

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 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.

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 i se afișează -1.

Restricții și 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 obtine loturi de valoare 2, 3, 4, 5 dintr-un singur jucator.
• Lotul de valoare 6 se poate obține din jucatorii cu valorile 2 si 4.
• Pentru valoarea 7 exista doua loturi posibile formate din jucătorii cu valorile 5 2 respectiv 3 4. Cel din urma lot are coeficientul de aroganta mai mic (adică max(3,4)-min(3,4)=1).