Iha has set up a potato farm to offer delicious french fries to Kalma. This potato farm can be viewed as a line of $N$ consecutive plots, numbered from 1 to $N$. Plot 1 is in the west, and plot $N$ is in the east. Unfortunately, some of the land Iha bought has rocks embedded in it, making it impossible to plant potatoes and difficult to walk on. However, after much effort, Iha planted some potatoes on this land and cultivated them diligently using the innovative technology of the 4th Industrial Revolution.

Finally, the time for harvest has arrived, and Iha is now ready to harvest the potatoes. Iha likes to move mechanically and follows these rules:

• Initially, Iha starts at a plot that has neither a rock nor a potato, and the initial direction of movement is east.
• Iha moves one plot at a time to the west or east, and each move takes 1 unit of time.
• If there is a potato planted in the plot Iha reaches, Iha harvests the potato and reverses the direction of movement.
  • There is at most one potato planted in each plot, and the time taken to harvest a potato and reverse direction is negligible.
• If there is a rock in the plot Iha reaches, Iha reverses the direction of movement.

Iha leaves the potato farm after moving one plot west from plot 1 or one plot east from plot $N$. This was Iha's plan, but after some thought, Iha realized that the number of potatoes harvested and the total time taken depend on the starting position. Iha even discovered that depending on the state of the farm, it might be impossible to leave the potato farm from some starting positions. Therefore, Iha wants to solve this problem quickly and devise a better method. Let's help Iha harvest the potatoes.

Input

The first line contains two natural numbers $N$ and $Q$, separated by a space ($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$). $N$ is the number of plots in the potato farm, and $Q$ is the number of queries.

The second line contains a string $S$ of length $N$. Each character of $S$ is 'P', 'R', or '.'. If the $i$-th character of $S$ ($1 \le i \le N$) is 'P', it means there is a potato in plot $i$; if it is 'R', there is a rock; and if it is '.', there is nothing.

From the third line, $Q$ lines follow, each containing a query. Each line consists of a natural number $x$ ($1 \le x \le N$), which means Iha wants to know what happens if the initial position is plot $x$. It is guaranteed that the $x$-th character of $S$ is '.', and all queries are distinct.

Each query must be calculated independently.

Output

For each query, print two integers $p$ and $t$ separated by a space on a single line. $p$ is the number of potatoes harvested when Iha starts at that position, and $t$ is the time taken if Iha can leave the potato farm, or -1 otherwise.

Examples

Input 1

6 3
.P.PR.
1
3
6

Output 1

1 3
2 11
0 1

Input 2

3 1
R.R
2

Output 2

0 -1

Input 3

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

Output 3

2 6
0 5
1 -1
3 18
0 4

Input 4

1 1
.
1

Output 4

0 1