Szatnia
Limit pamięci: 128 MB
W Bajtocji odbywa się doroczny zlot bogatych mieszkańców.
Zbierają się oni, by chwalić się swoimi zarobkami, butami Lebajtina
i innymi luksusowymi rzeczami.
Naturalnie, nie wszystkie rzeczy wnoszą na bankiet - płaszcze, kurtki
czy parasole zostawiają w szatni, by odebrać je, wychodząc.
Na nieszczęście bogaczy szajka bajtockich złodziei planuje włamać
się do szatni i ukraść część pozostawionych tam przedmiotów.
Póki co szef szajki przegląda zaproponowane przez gangsterów plany skoku.
Każdy plan wygląda następująco: złodzieje pojawiają się w szatni w chwili ,
zabierają przedmioty o wartości dokładnie i uciekają, przy czym
cały skok zajmuje im czas .
Szef gangu chciałby przede wszystkim wiedzieć, które z planów mają szansę
się udać, a które nie.
Plan ma szansę się udać, jeśli w chwili da się uzbierać przedmioty
o łącznej wartości dokładnie , w taki sposób, żeby do
momentu włącznie nikt nie przyszedł po żaden z kradzionych przedmiotów
(w takim wypadku zawiadomiłby ochronę i ucieczka nie udałaby się).
W szczególności, jeśli w chwili w ogóle nie da się dobrać przedmiotów o łącznej
wartości , plan zostaje odrzucony.
Znając moment przyniesienia i zabrania każdego przedmiotu, określ, które
plany mają szansę powodzenia, a które skazane są na porażkę.
Zakładamy, że jeśli przedmiot zostaje przyniesiony w momencie, w którym
złodzieje mają dokonać skoku, mogą go już ukraść (patrz test przykładowy).
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
(), reprezentująca liczbę przedmiotów, które zostaną
pozostawione w szatni.
W kolejnych wierszach znajdują się opisy przedmiotów.
Każdy z nich składa się z trzech liczb całkowitych ,
i (, ),
pooddzielanych pojedynczymi odstępami,
oznaczających kolejno: wartość przedmiotu, moment, w którym zostanie
przyniesiony do szatni, oraz moment, w którym zostanie z niej zabrany.
Następny wiersz zawiera liczbę ()
- liczbę planów przedstawionych przez szajkę.
Każdy z nich jest opisany w jednym wierszu przez trzy liczby całkowite
, i (, ,
), pooddzielane pojedynczymi odstępami,
oznaczające kolejno: moment, w którym złodzieje
weszliby do szatni, wartość, jaką chcą uzyskać, oraz czas, jaki zajmie im
kradzież.
W testach wartych 16% punktów zachodzi dodatkowy warunek
.
W innych testach, również wartych 16% punktów, wszystkie
przedmioty mają równe .
W jeszcze innych testach, wartych 24% punktów, wszystkie
zapytania mają równe .
Wyjście
Dla każdego planu szajki określ, czy plan da się zrealizować, tj. ukraść
przedmioty o wartości dokładnie i uciec, zanim ktoś upomni się o swoją
rzecz.
Jeśli plan jest wykonalny, Twój program powinien wypisać na standardowe
wyjście słowo TAK, a w przeciwnym wypadku słowo NIE.
Przykład
Dla danych wejściowych:
5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5
poprawną odpowiedzią jest:
TAK
NIE
TAK
TAK
NIE
Autor zadania: Jan Kanty Milczek.