Wstęp do programowania w C++

Grasz w odmianę gry Tetris na planszy o rozmiarach n wierszy na m kolumn. Wiesz jaki będzie następny spadający klocek. W tej odmianie gry, klocka nie można obracać ani przesuwać w prawo lub w lewo. Gracz zanim klocek zacznie poruszać się w dół planszy ustawia go w wybranym przez siebie przedziale kolumn, w którym będzie on spadał.

Twoim zadaniem jest stwierdzenie, czy można tak ustawić klocek, żeby zniknęła jedna linia.

Wejście

W pierwszej linii wejścia podana jest jedna liczba całkowita t ∈ [1;10] oznaczająca liczbę zestawów danych. W kolejnych liniach znajdują się zestawy danych. W pierwszej linii każdego zestawu danych podane są trzy liczby całkowite n, m ∈ [3;1000] i k ∈ [1;2] oznaczające odpowiednio liczbę wierszy i liczbę kolumn planszy oraz typ klocka, który będzie spadał. W kolejnych n wierszach znajduje się po m znaków opisujących obecną sytuację na planszy. Znak _ oznacza pole wolne, zaś znak # pole zajęte. Gwarantujemy, że na planszy nie znajduje się żaden wiersz w pełni zajęty oraz, że dwa pierwsze wiersze zawsze są wolne. Jednocześnie zapewniamy, że co najmniej jeden z boków każdego zajętego pola sąsiaduje z innym zajętym polem lub z podłożem planszy. Poniżej zamieszczone zostały możliwe typy klocka, który będzie spadał.

Gdy k = 1:

_##
##_

Gdy k = 2:

##_
_##

Wyjście

Dla każdego zestawu danych wypisujemy wynik w jednym z dwóch formatów. Jeżeli można tak ustawić klocek, aby zniknęła jedna linia to w pierwszym wierszu wyjścia dla tego zestawu danych powinniśmy wypisać słowo TAK. Po tym słowie podajemy przedział kolumn, w którym klocek powinien spadać. W kolejnych liniach wypisujemy sytuację na planszy tuż przed zniknięciem w pełni wypełnionego wiersza. Jeżeli nie można tak ustawić klocka, aby zniknęła jedna linia to wypisujemy słowo NIE.

Przykład

Wejście

2
5 5 1
_____
_____
###__
#____
##_##
3 6 2
______
______
###__#

Wyjście

NIE
TAK 3 5
______
__##__
######