Lizak

Limit pamięci: 64 MB

Bajtazar prowadzi w Bajtogrodzie sklep ze słodyczami. Wśród okolicznych dzieci najpopularniejszymi słodyczami są lizaki waniliowo-truskawkowe. Składają się one z wielu segmentów jednakowej długości, z których każdy ma jeden smak - waniliowy lub truskawkowy. Cena lizaka jest równa sumie wartości jego segmentów; segment waniliowy kosztuje jednego bajtalara, a truskawkowy dwa bajtalary.

Rys. 1: Przykładowy lizak o pięciu segmentach, trzech truskawkowych i dwóch waniliowych, ułożonych na przemian. Cena tego lizaka wynosi bajtalarów.

Obecnie Bajtazarowi został na składzie tylko jeden (za to być może bardzo długi) lizak. Sprzedawca zdaje sobie sprawę, że być może nikt nie będzie chciał go kupić w całości, dlatego dopuszcza możliwość łamania go na granicach segmentów w celu uzyskania lizaka o mniejszej długości. Fragment lizaka przeznaczony ostatecznie do sprzedaży musi pozostać niepołamany.

Doświadczenie pokazuje, że klienci najczęściej chcą kupić lizaka za całe swoje kieszonkowe. Bajtazar zastanawia się, dla wielu możliwych wartości , jak przełamać posiadany lizak tak, aby otrzymać lizak o cenie równej dokładnie bajtalarów. Ponieważ zadanie nie jest wcale proste, poprosił Cię o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz () oddzielone pojedynczym odstępem. Oznaczają one odpowiednio liczbę segmentów ostatniego pozostałego w sklepie lizaka oraz liczbę rozpatrywanych wartości . Segmenty lizaka są ponumerowane kolejno od 1 do . W drugim wierszu znajduje się -literowy opis lizaka, złożony z liter T i W, przy czym T oznacza segment truskawkowy, zaś W - waniliowy; -ta z tych liter opisuje smak -tego segmentu. W kolejnych wierszach znajdują się kolejne wartości do rozpatrzenia (), po jednej w wierszu.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie wierszy zawierających wyniki dla kolejnych wartości , po jednym wyniku w wierszu. Jeśli dla danej wartości nie da się wyłamać z lizaka spójnego fragmentu o wartości równej bajtalarów, należy wypisać słowo NIE. W przeciwnym przypadku należy wypisać dwie liczby oraz () oddzielone pojedynczym odstępem, takie że fragment lizaka złożony z segmentów o numerach od do włącznie ma wartość dokładnie bajtalarów. Jeśli istnieje wiele możliwych odpowiedzi, Twój program może podać dowolną z nich.

Przykład

Dla danych wejściowych:

5 3
TWTWT
5
1
7

poprawną odpowiedzią jest:

1 3
2 2
NIE

Wyjaśnienie do przykładu: Przykład opisuje lizak z rys. 1. Segmenty o numerach od 1 do 3 tworzą lizak postaci TWT, wart 5 bajtalarów. Segment numer 2 ma smak waniliowy i kosztuje 1 bajtalara. Z tego lizaka nie da się w żaden sposób uzyskać lizaka wartego 7 bajtalarów.

Autor zadania: Jakub Pachocki.