AlgoLiga 2018

Jasio włamywacz po raz kolejny

Jasio, który dzięki Twojej pomocy z powodzeniem otwiera wszelkie sejfy, postanowił, że podzieli się z Tobą łupem, ale tylko wtedy, gdy podział ten będzie sprawiedliwy. Mając dany ciąg wartości wszystkich zrabowanych kosztowności, musisz rozstrzygnąć, czy można tak podzielić je między dwie osoby, aby każda otrzymała połowę sumy wartości. Za każdym razem, kiedy będzie to możliwe, dostaniesz swoją dolę. Tak oto powstał nowy problem, którego rozwiązanie może się Tobie opłacić.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (d ≤ 100) oznaczająca liczbę włamań Jasia. Każde włamanie opisują dwa wiersze. Pierwszy z nich podaje liczbę n (1 ≤ n ≤ 1000) zrabowanych kosztowności. W wierszu drugim podanych jest n całkowitych dodatnich wartości poszczególnych łupów. Skądinąd wiadomo, że łączna wartość zrabowanych rzeczy nie przekracza 100 000.

Wyjście
Dla każdego przypadku, w osobnym wierszu należy wypisać słowo TAK albo NIE, w zależności o tego, czy jest możliwy, w rozumieniu Jasia, sprawiedliwy podział, czy też nie.

Przykład

Wejście
2
3
5 12 5
4
1 2 3 4

Wyjście
NIE
TAK