Iha założył farmę ziemniaków, aby przygotować pyszne frytki dla swojego przyjaciela. Farmę można postrzegać jako ciąg $N$ pól ułożonych w linii, ponumerowanych od 1 do $N$. Pole nr 1 znajduje się na zachodzie, a pole nr $N$ na wschodzie. Niestety, na części terenu, który kupił Iha, znajdują się skały, przez co nie można tam sadzić ziemniaków, a poruszanie się po nim jest utrudnione. Mimo to, dzięki ciężkiej pracy, Iha zasadził na tym terenie trochę ziemniaków i pielęgnował je, wykorzystując innowacyjne technologie czwartej rewolucji przemysłowej.

Nadszedł czas zbiorów i Iha zamierza zebrać ziemniaki. Ponieważ lubi poruszać się w sposób mechaniczny, przestrzega następujących zasad:

• Na początku Iha zaczyna na polu, na którym nie ma ani skały, ani ziemniaka, a jego początkowy kierunek ruchu to wschód.
• Iha porusza się o jedno pole na zachód lub wschód, a każdy ruch zajmuje 1 jednostkę czasu.
• Jeśli na polu, do którego dotrze Iha, rośnie ziemniak, Iha zbiera go i zmienia kierunek na przeciwny.
  • Na każdym polu może rosnąć maksymalnie jeden ziemniak, a czas potrzebny na zebranie ziemniaka i zmianę kierunku jest pomijalnie mały.
• Jeśli na polu, do którego dotrze Iha, znajduje się skała, Iha zmienia kierunek na przeciwny.

Iha opuszcza farmę po przejściu o jedno pole na zachód z pola nr 1 lub o jedno pole na wschód z pola nr $N$. Do tego momentu plan Ihy był jasny, ale po zastanowieniu zdał sobie sprawę, że liczba zebranych ziemniaków oraz całkowity czas potrzebny na zbiory różnią się w zależności od punktu startowego. Co więcej, odkrył, że w zależności od stanu farmy, z niektórych pozycji startowych w ogóle nie da się opuścić farmy. Pomóż Ihe szybko rozwiązać ten problem i opracować lepszą strategię.

Wejście

W pierwszej linii podane są dwie liczby naturalne $N$ oraz $Q$ oddzielone spacją ($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$). $N$ to liczba pól na farmie, a $Q$ to liczba zapytań Ihy.

W drugiej linii podany jest ciąg znaków $S$ o długości $N$. Każdy znak w $S$ to P, R lub .. Jeśli $i$-ty znak ($1 \le i \le N$) to P, oznacza to, że na polu $i$ rośnie ziemniak; jeśli R, oznacza to, że na polu znajduje się skała; jeśli ., oznacza to, że pole jest puste.

Od trzeciej linii podane jest $Q$ zapytań. Każda linia zawiera liczbę naturalną $x$ ($1 \le x \le N$), co oznacza, że Iha chce wiedzieć, co się stanie, jeśli jego pozycja początkowa to pole $x$. Gwarantuje się, że $x$-ty znak w $S$ to ., a wszystkie zapytania są różne.

Każde zapytanie należy obliczyć niezależnie.

Wyjście

Dla każdego zapytania wypisz w jednej linii dwie liczby całkowite $p$ oraz $t$ oddzielone spacją. $p$ to liczba zebranych ziemniaków, jeśli Iha zacznie z danej pozycji. $t$ to czas, jaki upłynął, jeśli Iha zdoła opuścić farmę, w przeciwnym razie $-1$.

Przykład

Wejście 1

6 3
.P.PR.
1
3
6

Wyjście 1

1 3
2 11
0 1

Wejście 2

3 1
R.R
2

Wyjście 2

0 -1

Wejście 3

11 5
..RP.RP.P.P
10
1
5
8
2

Wyjście 3

2 6
0 5
1 -1
3 18
0 4

Wejście 4

1 1
.
1

Wyjście 4

0 1