Problem description

Gry w kółko i krzyżyk nie trzeba nikomu przedstawiać. Jasio jest kiepski w tę grę, ciągle przegrywa ze swoim tatą. Zaczyna podejrzewać, że jego tata oszukuje (tzn. gra optymalnie). Chciałby również oszukiwać (grać optymalnie), ale nie potrafi. Pomóż mu!

Przykładowa sytuacja w grze w kółko i krzyżyk wygląda tak:

Pola planszy są numerowane od 1 do 9, z góry na dół, od lewej do prawej (na przykład środkowe górne pole ma numer 2).

Jasio niestety zanim wpadł na genialny pomysł poproszenia Cię o pomoc wykonał już kilka posunięć. Chciałby wiedzieć czy pomimo optymalnej gry swojego taty może jeszcze wygrać, a jeśli nie – to czy może chociaż zremisować. Oczywiście przy tym należy wskazać wygrywające/remisujące ruchy.

Grę zawsze rozpoczyna kółko. Jasio czasami gra jako kółko, a czasami jako krzyżyk, ale zawsze pyta Cię o pomoc wtedy, gdy jest jego ruch.

Optymalna gra taty polega na tym, że jeśli może wygrać niezależnie od ruchów Jasia to zawsze wygra. Jeśli może chociaż zremisować – to zawsze zremisuje. Być może podczas pierwszych ruchów dał Jasiowi trochę “forów” i nie grał optymalnie, ale Jasio nie może zakładać, że tata dalej będzie mu odpuszczał w przyszłych ruchach.

Napisz program, który: wczyta sytuację na planszy, wyznaczy czy Jasio może wygrać lub choćby zremisować grę (przy dalszej optymalnej grze jego taty), wyznaczy jaki powinien być następny ruch Jasia, aby to się mogło udać i wypisze wynik na standardowe wyjście.

Wejście

Wejście składa się z trzech wierszy. Każdy z nich składa się z trzech znaków. Każdy znak to O – oznaczający kółko, X – oznaczający krzyżyk lub . – oznaczające wolne pole.

Wyjście

Jeśli gra jest już zakończona i Jasio wygrał to w pierwszym i jedynym wierszu wyjścia należy wypisać TAK.

Jeśli Jasio może wygrać (ale jeszcze nie wygrał), w pierwszym wierszu wyjścia należy wypisać słowo TAK, a w drugim wierszu wyjścia rosnący ciąg cyfr oznaczający numery pól (zgodnie z numeracją z rysunku powyżej), w których Jasio powinien postawić swój symbol, aby mógł wygrać.

Jeśli gra jest już zakończona i Jasio zremisował to w pierwszym i jedynym wierszu wyjścia należy wypisać REMIS.

Jeśli Jasio nie może zapewnić sobie zwycięstwa, ale może zapewnić sobie remis (a gra jeszcze trwa) to w pierwszym wierszu wyjścia powinno się znaleźć słowo REMIS, a w drugim wierszu wyjścia rosnący ciąg cyfr oznaczający numery pól, w których Jasio powinien postawić swój symbol, aby zremisować.

Jeśli Jasio nie może sobie zapewnić nawet remisu – pierwszy i jedyny wiersz wyjścia powinien zawierać słowo NIE.

Cyfry na wyjściu nie powinny być oddzielane żadnymi odstępami.

Uwaga

Gwarantowane jest, że zawsze przedstawiona będzie “sensowna” sytuacja w grze (być może już zakończonej) w kółko i krzyżyk.

Na przykład następujące nie wystąpi w danych wejściowych:

OOO
XXX
...

ponieważ po postawieniu pięciu symboli gra zostanie już zakończona i nie będzie możliwe postawienie szóstego symbolu.

Gwarantowane jest również, że liczba symboli O jest równa liczbie symboli X lub jest dokładnie o jeden większa.

Przykład

OX.
...
...

TAK
457

..X
.O.
O..

REMIS
19

XXO
OOO
XOX

NIE