감자 농장

이하는 갊자에게 바삭한 감자튀김을 대접하려고 감자 농장을 꾸렸다. 이 농장은 $1$번 칸부터 $N$번 칸까지 일직선으로 이어진 땅이다. $1$번 칸이 가장 서쪽에 있고, $N$번 칸이 가장 동쪽에 있다. 안타깝게도 이하의 땅 일부에는 바위가 박혀 있어서 감자를 심을 수 없고, 그 위를 걷기도 불편하다. 그래도 이하는 애써서 일부 칸에 감자를 심었고, 4차 산업혁명의 혁신적인 기술로 정성껏 가꾸었다.

드디어 수확할 때가 되었다. 이하는 기계처럼 움직이는 것을 좋아해서 다음 규칙을 따라 움직인다.

• 처음에 이하는 바위도 감자도 없는 칸에 서 있으며, 최초 이동 방향은 동쪽이다.
• 이하는 한 칸씩 서쪽 또는 동쪽으로 이동한다. 이동할 때마다 $1$의 시간이 걸린다.
• 이하가 도달한 칸에 감자가 있으면, 감자를 수확하고 방향을 반대로 바꾼다.
  • 칸마다 감자는 최대 $1$개 심어져 있다. 수확과 방향 전환에 걸리는 시간은 무시할 만큼 작다.
• 이하가 도달한 칸에 바위가 있으면, 방향을 반대로 바꾼다.

이하는 $1$번 칸에서 서쪽으로 한 칸 이동하거나, $N$번 칸에서 동쪽으로 한 칸 이동하면 농장을 벗어난다.

여기까지가 이하의 원래 계획이었다. 그런데 다시 생각해 보니, 시작 위치에 따라 수확하는 감자의 개수와 총 소요 시간이 달라진다는 것을 알게 되었다. 또 땅의 상태에 따라서는 어떤 시작 위치에서든 농장을 벗어날 수 없다는 사실도 알아냈다. 이하는 이 문제를 빠르게 풀고 더 나은 방법을 찾고 싶어 한다. 감자를 수확하고 싶은 이하를 도와주자.

첫 번째 줄에 자연수 $N$, $Q$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 10^6$, $1 \leq Q \leq \min\left(N, 10^5\right)$) $N$은 감자 농장의 칸 수이고, $Q$는 이하의 질의 횟수이다.

두 번째 줄에는 길이 $N$의 문자열 $S$가 주어진다. $S$의 각 문자는 P, R, . 중 하나이다. $S$의 $i$번째 문자가 P이면 $i$번 칸에 감자가 심어져 있고, R이면 바위가 있으며, .이면 아무것도 없다.

세 번째 줄부터 $Q$개의 줄에 질의가 주어진다. 각 줄은 자연수 $x$ ($1 \leq x \leq N$)이다. 이는 이하가 시작 위치를 $x$번 칸으로 했을 때 어떻게 되는지 알고 싶다는 뜻이다. $S$의 $x$번째 글자는 항상 .이며, 모든 질의는 서로 다르다.

각 질의는 독립적으로 계산해야 한다.

질의마다 한 줄에 두 정수 $p$와 $t$를 공백으로 구분해 출력한다. $p$는 해당 위치에서 시작했을 때 수확한 감자의 개수이다. $t$는 농장을 벗어날 수 있다면 벗어날 때까지 걸린 시간이고, 벗어날 수 없다면 -1이다.