Problem description

Zapewne pierwszą rzeczą, jaka kojarzy się ludziom ze średniowieczem, jest stojący wśród lasów (bądź innych terenów zielonych) zamek. W końcu przecież, w zasadzie przez całą tę epokę historyczną, ludzie tylko i wyłącznie budowali zamki. Tak też będzie w tym zadaniu.

Pewien władca średniowiecznego imperium zwany Karolem Wspaniałym postanowił wybudować sobie zamek absolutnie niemożliwy do zdobycia; twierdzę, która przetrwa absolutnie każdy najazd. Oczywiście twierdza taka musi mieć solidnie zbudowane mury. Władca Karol wspaniały postanowił, że jego ściany będą miały nie jeden metr grubości, a dwa. Precyzyjniej mówiąc, mury zamkowe buduje się z bloków o wymiarach 2 × 1 × 1. Władca Karol Wspaniały wybudował już pierwszą warstwę muru w kształcie prostopadłościanu o wymiarach N × 1 × 2. Oczywiście brakuje jeszcze drugiej warstwy o dokładnie takich samych wymiarach, w końcu mur miał mieć dwa metry grubości. Jednak tutaj pojawia się pewien kłopot. Biorąc pod uwagę właściwości obronne muru, żaden z bloków z warstwy pierwszej nie może pokrywać się z żadnym z bloków z warstwy drugiej.

Przykładowo, jeśli w widoku od przodu warstwa pierwsza wygląda jak na rysunku pierwszym, to układ na rysunku drugim byłby poprawny – żaden blok z warstwy pierwszej nie pokrywa się z żadnym blokiem z warstwy drugiej. Natomiast układ na rysunku trzecim byłby niepoprawny, ponieważ bloki pionowe pokrywałyby się z blokami pionowymi z układu z rysunku pierwszego.

Twoim zadaniem będzie więc napisanie programu, który wczyta opis pierwszej warstwy muru i wyznaczy poprawny układ bloków w drugiej warstwie, czyli taki, w którym żaden z bloków z pierwszej warstwy nie pokrywa się z żadnym z bloków z drugiej warstwy.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna N oznaczająca długość pierwszej warstwy muru. W drugim wierszu znajduje się ciąg znaków S, składający się z liter H i V. Litera H odpowiada dwóm poziomym blokom, z których jeden postawiony jest na drugim, natomiast litera V odpowiada jednemu blokowi, ustawionemu pionowo. Przykładowo ciąg znaków VHVH reprezentuje układ z rysunku pierwszego, natomiast ciąg znaków VVVVVV reprezentuje układ z rysunku trzeciego.

Wyjście

W pierwszym wierszu standardowego wyjścia powinno znaleźć się jedno słowo TAK lub NIE w zależności od tego, czy istnieje poprawny układ bloków w warstwie drugiej. Jeśli odpowiedź jest twierdząca, to w drugim wierszu wyjścia należy wypisać ciąg znaków reprezentujący poprawny układ warstwy drugiej, w postaci opisanej w sekcji wejście. Jeśli istnieje wiele poprawnych odpowiedzi, możesz wypisać dowolną z nich.

Ograniczenia

2 ≤ N ≤ 100 000. Ciąg znaków S reprezentuje mur długości N.

Przykład

6
VHVH

TAK
HVHV

6
VVVVVV

TAK
HHH