Iha ha preparado una granja de patatas para ofrecer deliciosas patatas fritas a su conejo. Esta granja puede verse como un terreno continuo de celdas numeradas de la $1$ a la $N$. La celda $1$ está en el oeste y la celda $N$ está en el este. Desafortunadamente, algunas partes del terreno que Iha compró tienen rocas, lo que hace imposible plantar patatas y dificulta el caminar. Sin embargo, tras mucho esfuerzo, Iha plantó algunas patatas en este terreno y las cultivó con esmero utilizando tecnología innovadora de la cuarta revolución industrial.

Finalmente, ha llegado el momento de la cosecha e Iha se dispone a recoger las patatas. Como a Iha le gusta moverse de forma mecánica, sigue las siguientes reglas:

• Al principio, Iha comienza en una celda que no tiene ni rocas ni patatas, y la dirección inicial de movimiento es hacia el este.
• Iha se mueve una celda a la vez hacia el oeste o hacia el este, y cada movimiento toma $1$ unidad de tiempo.
• Si hay una patata plantada en la celda a la que llega Iha, cosecha la patata y cambia su dirección a la opuesta.
  • Como máximo hay una patata plantada por celda, y el tiempo necesario para cosechar una patata y cambiar de dirección es despreciable.
• Si hay una roca en la celda a la que llega Iha, cambia su dirección a la opuesta.

Iha sale de la granja de patatas después de moverse una celda al oeste desde la celda $1$ o una celda al este desde la celda $N$. Hasta aquí llegaba el plan de Iha, pero al reflexionar, se dio cuenta de que la cantidad de patatas cosechadas y el tiempo total requerido varían según la posición inicial. Incluso descubrió que, dependiendo del estado de la granja, en algunas posiciones iniciales es imposible salir de la granja de patatas. Por lo tanto, Iha quiere resolver este problema rápidamente y encontrar un método mejor. Ayudemos a Iha a cosechar las patatas.

Entrada

La primera línea contiene dos números naturales $N$ y $Q$ separados por un espacio ($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$). $N$ es el número de celdas de la granja de patatas y $Q$ es el número de consultas de Iha.

La segunda línea contiene una cadena $S$ de longitud $N$. Cada carácter de $S$ es 'P', 'R' o '.'. Si el $i$-ésimo carácter de $S$ ($1 \le i \le N$) es 'P', significa que hay una patata plantada en la celda $i$; si es 'R', significa que hay una roca; y si es '.', significa que no hay nada.

A partir de la tercera línea, se proporcionan $Q$ líneas con las consultas de Iha. Cada línea consiste en un número natural $x$ ($1 \le x \le N$), lo que significa que Iha quiere saber qué sucederá si su posición inicial es la celda $x$. Se garantiza que el $x$-ésimo carácter de $S$ es '.', y todas las consultas son distintas.

Cada consulta debe calcularse de forma independiente.

Salida

Para cada consulta, imprima en una línea dos números enteros $p$ y $t$ separados por un espacio. $p$ es la cantidad de patatas cosechadas cuando Iha comienza en esa posición, y $t$ es el tiempo transcurrido si Iha puede salir de la granja de patatas, o $-1$ en caso contrario.

Ejemplos

Entrada 1

6 3
.P.PR.
1
3
6

Salida 1

1 3
2 11
0 1

Entrada 2

3 1
R.R
2

Salida 2

0 -1

Entrada 3

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

Salida 3

2 6
0 5
1 -1
3 18
0 4

Entrada 4

1 1
.
1

Salida 4

0 1