为了给他的朋友准备美味的炸薯条，李哈（Iha）经营着一个土豆农场。这个农场可以看作是从第 $1$ 号格子到第 $N$ 号格子连成的一排土地。第 $1$ 号格子在西边，第 $N$ 号格子在东边。不幸的是，李哈买下的土地中有些地方埋着岩石，不仅无法种植土豆，走起来也不方便。但在努力之后，李哈还是在土地上种了一些土豆，并利用第四次工业革命的创新技术进行了精心培育。

终于到了收获的季节，李哈准备收获土豆。李哈喜欢机械化的行动方式，他遵循以下规则进行移动：

• 起初，李哈从一个既没有岩石也没有土豆的格子开始，初始移动方向为东。
• 李哈每次向西或向东移动一格，每次移动耗时 $1$。
• 如果李哈到达的格子里种有土豆，他会收获该格的土豆，并将移动方向反转。
  • 每个格子最多种植 $1$ 个土豆，收获土豆和反转方向的时间忽略不计。
• 如果李哈到达的格子里有岩石，他会将移动方向反转。

当李哈从第 $1$ 号格子向西移动，或从第 $N$ 号格子向东移动时，他就会离开土豆农场。

这原本是李哈的计划，但他意识到，根据初始位置的不同，能收获的土豆数量和总耗时也会有所不同。甚至根据农场的状态，在某些起始位置，他可能永远无法离开土豆农场。因此，李哈希望快速解决这个问题，并构思出更好的方法。让我们来帮助想要收获土豆的李哈。

输入格式

第一行包含两个自然数 $N$ 和 $Q$，中间用空格分隔。($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$)。$N$ 是土豆农场的格子数，$Q$ 是李哈的询问次数。

第二行给出一个长度为 $N$ 的字符串 $S$。$S$ 中的每个字符为 P、R 或 .。如果 $S$ 的第 $i$ ($1 \le i \le N$) 个字符是 P，表示第 $i$ 号格子种有土豆；如果是 R，表示有岩石；如果是 .，表示什么都没有。

从第三行开始，共有 $Q$ 行，每行给出一个自然数 $x$ ($1 \le x \le N$)，表示李哈想知道如果将初始位置设为第 $x$ 号格子会发生什么。保证 $S$ 的第 $x$ 个字符为 .，且所有询问的 $x$ 互不相同。

每个询问需要独立计算。

输出格式

对于每个询问，输出一行，包含两个整数 $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