Aveti la dispozitie N obiecte, numerotate de la 1 la N. Fiecare obiect i are o greutate wi si un cost ci. O submultime SN a celor N obiecte poate contine fiecare obiect cel mult o data. Greutatea unei submultimi SN este egala cu suma greutatilor obiectelor din SN, iar costul unei submultimi SN este egal cu suma costurilor obiectelor din SN. Fie cmin costul minim al unei submultimi SN a carei greutate este egala cu o valoare data S. Se doreste clasificarea fiecarui obiect i intr-una din urmatoarele 3 categorii:
categoria 1: obiectul i face parte din categoria 1 daca apartine fiecarei submultimi avand greutatea egala cu S si costul egal cu cmin (altfel spus, nu exista nicio submultime SN cu greutatea S si costul cmin care sa nu contina obiectul i)
categoria 2: obiectul i face parte din categoria 2 daca nu face parte din categoria 1, dar apartine cel putin unei submultimi SN a carei greutate este S si al carei cost este cmin
categoria 3: obiectul i face parte din categoria 3 daca nu apartine niciunei submultimi SN avand greutatea S si costul cmin
Cerinta
Scrieti un program care sa determine pentru fiecare obiect i categoria din care face parte acesta.
Date de intrare
Fisierul de intrare ic.in contine pe prima linie numarul natural T, reprezentand numarul de teste descrise in fisier. In continuare sunt descrise cele T teste. Prima linie a fiecarui test contine numerele naturale N si S, separate printr-un spatiu. Urmatoarele N linii descriu cele N obiecte: a i-a dintre aceste N linii contine numerele naturale wi si ci (separate printr-un spatiu).
Date de iesire
In fisierul de iesire ic.out veti afisa T linii. A i-a dintre aceste linii va contine raspunsul pentru al i-lea test dat in fisierul de intrare. Raspunsul pentru un test consta dintr-un sir de N caractere, unde N este numarul de obiecte din testul respectiv. Al j-lea caracter din acest sir reprezinta categoria din care face parte obiectul j. Cele N caractere pot lua una dintre valorile '1', '2' sau '3' si nu sunt separate prin spatii.
Restrictii
1 <= T <= 100
1 <= N <= 200
1 <= S <= 700
1 <= wi <= 10
1 <= ci <= 10
Se garanteaza ca, pentru fiecare test dat in fisierul de intrare, va exista cel putin o submultime de obiecte a carei greutate sa fie egala cu S.
Exemplu
ic.in
ic.out
2
6 10
3 2
2 6
3 4
4 10
4 11
5 8
2 2
2 3
2 3
122232
22
Asist. univ. dr. ing. Mugurel Ionut Andreica
Facultatea de Automatica si Calculatoare,
Universitatea Politehnica din Bucuresti