Иха решил разбить картофельную ферму, чтобы принести вкусную картошку фри своей возлюбленной. Эту ферму можно представить как ряд из $N$ последовательных участков, пронумерованных от 1 до $N$. Участок 1 находится на западе, а участок $N$ — на востоке. К сожалению, на некоторых участках земли, купленной Ихой, есть камни, из-за которых там нельзя посадить картофель, да и ходить по ним неудобно. Однако после долгих усилий Иха всё же посадил картофель на части этой земли и бережно ухаживал за ним, используя инновационные технологии 4-й промышленной революции.

Наконец пришло время сбора урожая, и Иха собирается собрать картофель. Поскольку Иха любит механические движения, он перемещается по ферме, соблюдая следующие правила:

• Изначально Иха начинает движение с участка, на котором нет ни камней, ни картофеля, а начальное направление движения — на восток.
• Иха перемещается на один участок на запад или восток, каждое перемещение занимает 1 единицу времени.
• Если на участке, куда прибыл Иха, посажен картофель, он собирает его и меняет направление движения на противоположное.
  • На каждом участке может быть посажено не более одного картофеля, а время на сбор картофеля и смену направления пренебрежимо мало.
• Если на участке, куда прибыл Иха, есть камень, он меняет направление движения на противоположное.

Иха покидает картофельную ферму, если перемещается на один участок западнее участка 1 или на один участок восточнее участка $N$. Изначально это был весь план Ихи, но, подумав, он понял, что количество собранного картофеля и общее затраченное время зависят от начальной позиции. Более того, он обнаружил, что в зависимости от состояния фермы, из некоторых начальных позиций покинуть ферму невозможно. Помогите Ихе быстро решить эту задачу и найти лучший способ сбора урожая.

Входные данные

В первой строке заданы два натуральных числа $N$ и $Q$, разделенные пробелом ($1 \le N \le 10^6$, $1 \le Q \le \min(N, 10^5)$). $N$ — количество участков на ферме, а $Q$ — количество запросов Ихи.

Во второй строке задана строка $S$ длины $N$. Каждый символ строки $S$ — это 'P', 'R' или '.'. Если $i$-й символ строки $S$ ($1 \le i \le N$) равен 'P', это означает, что на участке $i$ посажен картофель; если 'R', то на участке есть камень; если '.', то на участке ничего нет.

Начиная с третьей строки, заданы $Q$ запросов. Каждая строка содержит натуральное число $x$ ($1 \le x \le N$), что означает, что Иха хочет узнать результат, если его начальной позицией будет участок $x$. Гарантируется, что $x$-й символ строки $S$ равен '.', и все запросы различны.

Каждый запрос должен вычисляться независимо.

Выходные данные

Для каждого запроса выведите в одной строке два целых числа $p$ и $t$, разделенных пробелом. $p$ — количество собранного картофеля, если Иха начал с этой позиции. $t$ — время, затраченное на то, чтобы покинуть ферму, или -1, если покинуть ферму невозможно.

Примеры

Примеры 1

6 3
.P.PR.
1
3
6

1 3
2 11
0 1

Примеры 2

3 1
R.R
2

0 -1

Примеры 3

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

2 6
0 5
1 -1
3 18
0 4

Примеры 4

1 1
.
1

0 1