AlgoLiga 2018

Możliwości Antka i Basi w wymyślaniu nowych gier wydają się wręcz nieograniczone. Ich najnowszy pomysł to gra, która toczy się w wielowymiarowym układzie współrzędnych kartezjańskich, a dokładniej w tej jego części, w której współrzędne wszystkich punktów są nieujemne. Do gry używa się kilku rodzajów figur, które na początku ustawione są w wybranych punktach kratowych (polach planszy). Gracze wykonują ruchy na zmianę i muszą zawsze przesunąć jedną dowolną figurę do innego punktu kratowego o nieujemnych współrzędnych znajdującego się bliżej początku układu. Takie przesunięcie musi być wykonane zgodnie z regułami, które dotyczą wybranej figury. W jednym punkcie może się jednocześnie znajdować dowolna liczba figur. Figurę, która po ruchu znajdzie się w punkcie o wszystkich współrzędnych zerowych (punkt O), zdejmuje się z planszy. Przegrywa ten, kto nie może wykonać ruchu.

Dzieci ustaliły, że będą trzy rodzaje figur: wieża, goniec i skoczek. Każda z nich będzie też miała określoną rangę (dodatnia liczba R), która oznacza, o ile maksymalnie punktów kratowych można taką figurę przesunąć w jednym ruchu. Zakładając, że figura znajduje się w punkcie (x₁,x₂,...,x_k), zasady opisujące dozwolone ruchy są następujące:

• Wieża.  Aby przesunąć ją o d pól, należy zmniejszyć o d wartość tylko jednej wybranej współrzędnej x_i (d ≤ x_i, 1 ≤ d ≤ R).
• Goniec. Jeśli chcemy przesunąć tę figurę o d punktów, to należy jedną wybraną współrzędną x_i zmniejszyć o d, a pozostałe współrzędne o min(d,x_i) (d ≤ x_i, 1 ≤ d ≤ R).
• Skoczek. Tę figurę przesuwamy tylko po punktach kratowych znajdujących się na odcinku łączącym punkt początkowy z punktem O. W jednym ruchu skoczka przesuwamy o co najmniej 1 i co najwyżej R takich punktów.

Kilka przykładów dla dwuwymiarowej planszy (bez uzwględniania rangi figury): 
Wieża znajdująca się na polu (2,1) może zostać przesunięta do jednego z punktów: (1,1), (0,1), (2,0).
Gońca z punktu (2,5) można przesunąć do jednego z punktów: (1,4), (0,3), (0,2), (0,1), (0,0).
Skoczek z punktu (6,9) może przejść na jedno z pól: (2,6), (1,3), (0,0).

Zakładając optymalną grę obojga dzieci, chcemy się dowiedzieć, czy rozpoczynający ma szansę na wygraną. Jeśli tak jest, to dodatkowo trzeba podać, którą figurą należy wykonać pierwszy ruch i o ile punktów ją przesunąć.

Wejście

Najpierw liczba testów t (1 ≤ t ≤ 10).
W pierwszej linii każdego testu dwie liczby całkowite: k - liczba wymiarów planszy (1 ≤ k ≤ 100), n - liczba figur (1 ≤ n ≤ 1000).
W każdej z kolejnych n linii opis jednej figury w następującym formacie: T R x_i (dla i=1..k). Gdzie:
T - jedna litera oznaczająca typ figury ('W' - wieża, 'G' - goniec, 'S' - skoczek).
R - liczba całkowita oznaczająca rangę figury (1 ≤ R ≤ 10⁹).
x_i (dla i=1..k) - kolejne współrzędne punktu, w którym figura znajduje się na początku gry (0 ≤ x_i ≤ 10⁹). Co najmniej jedna z tych współrzędnych ma wartość niezerową. 

Wyjście

Dla każdego testu, w osobnej linii słowo "NIE" jeśli rozpoczynający grę nie ma szansy na wygraną albo słowo "TAK" w przeciwnym wypadku.
W tej drugiej sytuacji, dodatkowo należy wypisać: numer figury, którą należy wykonać pierwszy ruch gwarantujący wygraną (figury numerujemy od 1 do n) oraz liczbę punktów, o które należy ją przesunąć, a gdy tą figurą jest wieża, to jeszcze numer współrzędnej (możliwie najniższy od 1 do k), której ruch ma dotyczyć.
Jeśli jest kilka figur, którymi można wykonać wygrywający ruch, to trzeba wskazać tę, którą wymaga przesunięcia o najmniej punktów. Jeżeli poprzedni warunek nie jest rozstrzygający, to należy wybrać figurę o niższym numerze. 

Przykład

Wejście:
4
4 1
W 5 1 2 4 4
2 3
S 3 5 10
G 7 4 3
W 5 4 10
3 4
G 7 5 7 0
W 3 4 4 4
G 5 0 0 3
S 6 8 8 12
3 1
S 2 4 6 8 

Wyjście:
TAK 1 1 2
TAK 2 3
NIE
TAK 1 2