Iha a créé une ferme de pommes de terre pour offrir de délicieuses frites à Kalja. Cette ferme peut être vue comme une étendue de terre composée de $N$ cases consécutives, numérotées de 1 à $N$. La case 1 est située à l'ouest et la case $N$ est située à l'est. Malheureusement, certaines parties du terrain acheté par Iha contiennent des rochers, ce qui rend impossible la plantation de pommes de terre et rend la marche difficile. Cependant, après beaucoup d'efforts, Iha a planté des pommes de terre sur une partie de ce terrain et l'a cultivé avec soin en utilisant des technologies innovantes de la quatrième révolution industrielle.

Le moment de la récolte est enfin arrivé, et Iha s'apprête à récolter les pommes de terre. Comme Iha aime les mouvements mécaniques, il se déplace en respectant les règles suivantes :

• Au départ, Iha commence sur une case qui ne contient ni rocher ni pomme de terre, et la direction initiale est vers l'est.
• Iha se déplace d'une case vers l'ouest ou vers l'est, et chaque déplacement prend 1 unité de temps.
• Si la case atteinte par Iha contient une pomme de terre, Iha récolte la pomme de terre présente sur le terrain et change de direction.
  • Chaque case contient au maximum une pomme de terre, et le temps nécessaire pour récolter une pomme de terre ou changer de direction est négligeable.
• Si la case atteinte par Iha contient un rocher, Iha change de direction.

Iha quitte la ferme après s'être déplacé d'une case vers l'ouest depuis la case 1, ou d'une case vers l'est depuis la case $N$. C'était le plan initial d'Iha, mais après réflexion, il a réalisé que le nombre de pommes de terre récoltées et le temps total nécessaire varient en fonction de la position de départ. Il a même découvert qu'en fonction de l'état de la ferme, il est impossible de quitter la ferme depuis certaines positions de départ. Par conséquent, Iha souhaite résoudre ce problème rapidement pour concevoir une meilleure méthode. Aidons Iha à récolter ses pommes de terre.

Entrée

La première ligne contient deux entiers naturels $N$ et $Q$ séparés par un espace ($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$). $N$ est le nombre de cases de la ferme, et $Q$ est le nombre de requêtes d'Iha.

La deuxième ligne contient une chaîne de caractères $S$ de longueur $N$. Chaque caractère de $S$ est 'P', 'R', ou '.'. Si le $i$-ième caractère de $S$ ($1 \le i \le N$) est 'P', cela signifie qu'il y a une pomme de terre sur la case $i$. S'il est 'R', cela signifie qu'il y a un rocher, et s'il est '.', cela signifie qu'il n'y a rien.

À partir de la troisième ligne, $Q$ lignes suivent, chacune contenant une requête. Chaque ligne est composée d'un entier naturel $x$ ($1 \le x \le N$), ce qui signifie qu'Iha veut savoir ce qui se passera s'il choisit la case $x$ comme position initiale. Il est garanti que le $x$-ième caractère de $S$ est '.', et toutes les requêtes sont distinctes.

Chaque requête doit être calculée indépendamment.

Sortie

Pour chaque requête, affichez sur une ligne deux entiers $p$ et $t$ séparés par un espace. $p$ est le nombre de pommes de terre récoltées lorsqu'Iha commence à cette position, et $t$ est le temps écoulé si Iha parvient à quitter la ferme, ou -1 sinon.

Exemples

Exemples 1

6 3
.P.PR.
1
3
6

1 3
2 11
0 1

Exemples 2

3 1
R.R
2

0 -1

Exemples 3

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

2 6
0 5
1 -1
3 18
0 4

Exemples 4

1 1
.
1

0 1