Problem description

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.

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

3 4
PSSS
SPPS
PPPS

TAK
PDPPD

3 4
PSPP
SPSP
PSPP

NIE

1 1
P

NIE

3 4
SSSS
PSPS
PPSP

TAK
DPPDP

2 4
PPSP
SSPS

NIE