19536번 - 감자 농장

이하는 갊자에게 맛있는 감자튀김을 바치기 위해 감자 농장을 꾸렸다. 이 감자 농장은 $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\ (1 \leq i \leq N)$번째 문자가 P이면 $i$번 칸에 감자가 심어져 있음을 의미하고, R이면 바위가 있음을 의미하며, .이면 아무 것도 없음을 의미한다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 이하의 질의가 주어진다. 각 줄은 자연수 $x$로 이루어져 있다. $(1 \leq x \leq N)$ 이는 이하가 초기 위치를 $x$번 칸으로 삼았을 때 어떻게 될지 알고 싶음을 의미한다. $S$의 $x$번째 글자는 .임이 보장되며, 모든 질의는 서로 다르다.

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

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