Problem description

Jasio lubi grać w grę planszową o nazwie Gra w skakanie. Plansza do gry składa się z N + 1 pól ponumerowanych od 0 do N. Ponadto w zestawie jest również kość M-ścienna, z liczbami od 1 do M. Początkowo pionek Jasia znajduje się w polu o numerze 0. Celem gry jest dojście do ostatniego, N-tego pola. W każdej rundzie Jasio rzuca kością i przemieszcza się w przód o taką liczbę pól, jaka wypadła w rzucie kością. Jednakże, niektóre pola są zabronione i jeżeli w jakimkolwiek momencie Jasio miałby stanąć na takim polu, to musi wrócić się na sam początek planszy.

Jasio zaczął zastanawiać się, ile minimalnie rzutów kością musiałby wykonać, żeby bezpiecznie, bez żadnego cofnięcia, dotrzeć do N-tego pola? Jasio jest mały, żeby samemu odpowiedź na to pytanie, dlatego poprosił Cię o pomoc. Napisz program, który wyznaczy minimalną liczbę rzutów kością oraz jakie wartości musiałyby wypaść, aby Jasio dotarł do końca planszy!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz M oznaczające odpowiednio długość planszy oraz rozmiar kości. W następnym wierszu znajduje się ciąg N + 1 znaków . oraz X oznaczające odpowiednio wolne i zablokowane pole. Pierwszy znak odpowiada polu zerowemu, a ostatni (N + 1-wszy) polu N-temu.

Wyjście

Jeżeli nie istnieje ciąg ruchów, który pozwoli Jasiowi dotrzeć do końca planszy, należy wypisać -1. W przeciwnym wypadku, należy wypisać dwa wiersze. W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą minimalną liczbę rzutów potrzebną do wykonania, aby dojść do ostatniego pola planszy. W następnym wierszu należy wypisać najmniejszą leksykograficznie serię rzutów, która osiągnęłaby ten cel. Mówimy, że k-elementowy ciąg a₁, …, a_k jest mniejszy leksykograficznie od ciągu b₁, …, b_k, gdy a₁ = b₁, …, a_i = b_i oraz a_i + 1 < b_i + 1 dla pewnego 1 ≤ i < k.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ N. Możesz założyć, że pola o numerach 0 i N są zawsze wolne.

Podzadania

Twój program otrzyma 50% punktów za dany test, jeżeli pierwszy wiersz wyjścia będzie poprawny.

Przykład

5 2
.X..X.

3
2 1 2 

5 2
......

3
1 2 2 

5 2
.XXXX.

-1