Mapa

Limit pamięci: 128 MB

Spotykasz na szlaku roztrzęsioną turystkę. Dostała ona od męża nowiuteniką mapę, której teraz nie może poskładać. Postanowiłeś jej pomóc. Mapa składa się z kwadratów jednostkowych (tj. takich, których już nie można złożyć).

Pomiędzy każdą parą kwadratów jednostkowych są zagięcia: niektóre wypukłe, a inne wklęsłe. Mapę można składać wzdłuż pionowych i poziomych prostych, przechodzących pomiędzy kwadratami jednostkowymi, o ile spełnione są dwa warunki.

Po pierwsze, wszystkie zgięcia na tej prostej muszą być tego samego rodzaju. Po drugie, zagięcia, które zetkną się ze sobą po złożeniu, powinny być ze sobą zgodne, tzn. być przeciwnego typu przed wykonaniem zgięcia.

Twoje zadanie polega na tym, by powiedzieć turystce, jak poskładać mapę, by miała rozmiar kwadratu jednostkowego.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby naturalne i (), oznaczające odpowiednio wysokość i szerokość mapy; kwadrat jednostkowy ma wymiary .

Kolejne wierszy zawiera opisy zagięć pomiędzy kwadratami jednostkowymi sąsiadującymi w poziomie. W -tym z nich znajduje się ciąg znaków \^ (zagięcie wypukłe) lub v (zagięcie wklęsłe), opisujący kolejne zagięcia w -tym wierszu kwadratów jednostkowych. Następne wierszy opisy zagięć pomiędzy kwadratami jednostkowymi sąsiadującymi w pionie. W -tym z nich znajduje się ciąg znaków \^ (zagięcie wypukłe) lub v (zagięcie wklęsłe), opisujący kolejne zagięcia pomiędzy odpowiednimi kwadratami w -tej oraz -szej kolumnie kwadratów jednostkowych.

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać jedno słowo TAK lub NIE, w zależności od tego, czy mapę da się poskładać. Jeśli jest to wykonalne, kolejny wiersz powinien zawierać jedną liczbę całkowitą , oznaczającą liczbę kroków potrzebnych do jej złożenia. Każdy z kolejnych wierszy powinien opisywać wykonanie jednego złożenia w postaci jednego znaku oraz liczby całkowitej . Znak to | lub -, określa on czy wykonujemy złożenie wzdłuż pionowej, czy poziomej prostej. Jeśli wykonujemy pionowe złożenie, przebiega ono wzdłuż prostej pomiędzy kolumnami kwadratów jednostkowych numer oraz . Jeśli zaś wykonujemy złożenie poziome, przebiega ono wzdłuż prostej pomiędzy wierszami kwadratów jednostkowych numer oraz . Numeracja kwadratów jest ustalona na początku i nie zmienia się w czasie składania. Gdy po złożeniu mapy nakłada się się na siebie kilka prostych, można używać numerów dowolnych z nich.

W przypadku gdy istnieje poprawnych rozwiązań, możesz wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

2 3
^^
^v
v^^

poprawną odpowiedzią jest:

TAK
3
| 1
- 1
| 2

Rysunek mapy z testu przykładowego. Pogrubione krawędzie oznaczają zgięcia wklęsłe, a zwykłe - wypukłe.

Autorzy zadania: Piotr Niedźwiedź i Jakub Pawlewicz.