問題 E. ジャガイモ農場

イハは、ジャガイモが大好きな友人のためにジャガイモ農場を作りました。このジャガイモ農場は、1番から $N$ 番までの区画が一直線に並んでいる土地と見なすことができます。1番の区画が西端にあり、$N$ 番の区画が東端にあります。残念ながら、イハが購入した土地の一部には岩が埋まっており、ジャガイモを植えることができないだけでなく、歩き回るのも不便でした。しかし、努力の末にイハはこの土地の一部にジャガイモを植え、第4次産業革命の革新的な技術を用いて懸命に育てました。

ついに収穫の時が近づき、イハはジャガイモを収穫しようとしています。イハは機械的に動くことを好むため、以下のルールに従って移動します。

• 最初は、岩もジャガイモもない区画から開始し、最初の移動方向は東です。
• イハは1区画ずつ西または東に移動し、1回の移動につき1の時間がかかります。
• イハが到達した区画にジャガイモが植えられている場合、イハはその区画のジャガイモを収穫し、移動方向を反転させます。
  • ジャガイモは各区画に最大1つ植えられており、ジャガイモを収穫する時間および方向転換にかかる時間は無視できるほど小さいものとします。
• イハが到達した区画に岩がある場合、イハは移動方向を反転させます。

イハは、1番の区画から西へ1区画移動するか、$N$ 番の区画から東へ1区画移動することで、ジャガイモ農場の外に出ます。ここまでがイハの計画でしたが、よく考えてみると、開始位置によって収穫できるジャガイモの数と総所要時間が異なることに気づきました。さらに、農場の状態によっては、特定の開始位置からはジャガイモ農場の外に出られない場合があることも分かりました。そこでイハは、この問題を素早く解き、より良い方法を考え出そうとしています。ジャガイモを収穫したいイハを助けてあげましょう。

入力

1行目には、2つの自然数 $N, Q$ が空白区切りで与えられます。($1 \le N \le 10^6, 1 \le Q \le \min(N, 10^5)$) $N$ はジャガイモ農場の区画数、$Q$ はイハのクエリの回数です。

2行目には、長さ $N$ の文字列 $S$ が与えられます。$S$ の各文字は P、R、または . です。$S$ の $i$ ($1 \le i \le N$) 番目の文字が P ならば $i$ 番目の区画にジャガイモが植えられていることを意味し、R ならば岩があることを意味し、. ならば何も植えられていないことを意味します。

3行目から $Q$ 行にわたって、イハのクエリが与えられます。各行は自然数 $x$ で構成されています。($1 \le x \le N$) これは、イハが初期位置を $x$ 番目の区画とした場合にどうなるかを知りたいことを意味します。$S$ の $x$ 番目の文字は . であることが保証されており、すべてのクエリは互いに異なります。

各クエリは独立して計算する必要があります。

出力

各クエリについて、1行ずつ、2つの整数 $p$ と $t$ を空白区切りで出力します。$p$ はイハがその位置から開始したときに収穫したジャガイモの数です。$t$ はイハがジャガイモ農場の外に出ることができる場合にかかった時間であり、出ることができない場合は -1 です。

入出力例

入力 1

6 3
.P.PR.
1
3
6

出力 1

1 3
2 11
0 1

入力 2

3 1
R.R
2

出力 2

0 -1

入力 3

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

出力 3

2 6
0 5
1 -1
3 18
0 4

入力 4

1 1
.
1

出力 4

0 1