Problem description


Dieta cud
(E)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Jasiu dostał zalecenie od dietetyka, że: musi ograniczyć spożywanie niezdrowych potraw oraz zacząć “trzymać linię”. Jak usłyszał, tak zrobił. Na następne N dni zaplanował po M potraw. Rozpisał je wszystkie w prostokąt N × M i zastanawia się, jak dotrzymać zaleceń fachowca.

 

magic spell

 

Każdą z potraw opisał jako pizzo-podobną lub sałatko-podobną, co oznacza tyle, że potrawa zwiększa lub zmniejsza jego wagę. Jasiu poprzez “trzymanie linii”, zrozumiał dwie następujące rzeczy:

  1. Potrawy, które zje, stanowią ścieżkę w prostokącie z górnego lewego do dolnego prawego rogu, poruszając się wyłącznie w prawo lub w dół.

  2. Nie może przytyć, ani schudnąć, czyli potraw pizzo-podobnych ma być tyle co salatko-podobnych.

Czy dla podanych potraw na najbliższe N dni, możliwe jest stworzenie diety cud dla Jasia?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M opisujące wymiary prostokąta Jasia.

W następnych N wierszach znajduje się ciąg o długości M złożony z liter P oraz S, opisujący czy w danym polu potrawa jest pizzo-podobna lub sałatko-podobna.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się słowo NIE, gdy nie jest możliwe stworzenie diety cud. Jeśli istnieje, wypisz TAK oraz słowo długości (N+M−2), składające się z liter P (ruch w prawo) i D (ruch w dół), opisujące ścieżkę diety Jasia.

Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.

Ograniczenia

1 ≤ N, M ≤ 1000

Przykład

Wejście Wyjście
3 4
PSSS
SPPS
PPPS
TAK
PDPPD
Wejście Wyjście
3 4
PSPP
SPSP
PSPP
NIE
Wejście Wyjście
1 1
P
NIE
Wejście Wyjście
3 4
SSSS
PSPS
PPSP
TAK
DPPDP
Wejście Wyjście
2 4
PPSP
SSPS
NIE