A screenshot of :kevin: in action.

On the second day of school, the computer science teacher shows some more impressive screensavers on the computer. This time, the screensaver called :kevin: stands out to you, mainly due to the simple rules that govern :kevin:.

Upon careful analysis, :kevin: can be represented as an array of $N$ mirrors placed along a horizontal line. There is $1$ unit distance between adjacent mirrors, and the mirrors can be oriented in two ways, horizontally and vertically.

A ball enters the array from the left end, and is moving to the right at a rate of $1$ unit distance per second. The first bounce occurs at $0.5$ seconds. The rules of bouncing are in the following list:

• If the ball hits a horizontal mirror, the ball's direction stays the same and the mirror becomes vertical.
• If the ball hits a vertical mirror, the ball will move in the opposite direction and the mirror becomes horizontal.

As a fan of :kevin:, you want to implement this screensaver yourself! Firstly, the ball tends to leave the array too quickly. Given the initial conditions, your task is to calculate the number of seconds that the ball will stay in the array. Since this number may be too small for your own taste, there will be $T$ updates. On the $i^{\text{th}}$ update, change the initial orientation of the ${m_i}^{\text{th}}$ mirror and output the new number of seconds.

Constraints

In all subtasks:

$1\le N,T$

$1\le m_i\le N$

Subtask	Points	$N$	$T$
1	25	$N\le 10$	$T\le 10000$
2	25	$N\le 10000$	$T\le 10$
3	50	$N\le 100000$	$T\le 100000$

Input Specification

The first line will contain two space-separated integers, $N$ and $T$.

The second line will contain $N$ characters. The $i^{\text{th}}$ character represents the initial orientation of the $i^{\text{th}}$ mirror.

On the next $T$ lines, the $i^{\text{th}}$ line will contain the integer $m_i$. The initial orientation of the ${m_i}^{\text{th}}$ mirror will be changed.

Output Specification

For each of the $T$ changes, on an empty line, output the number of seconds that the ball will stay in the array. It is guaranteed that this number will not exceed ${10}^6$.

Sample Input

5 4
|--|-
1
1
1
4

Sample Output

7
1
7
5

Explanation for Sample Output

On the first change, the initial array is set to ---|-.

The ball leaves the array after $7$ seconds.

On the second change, the initial array is set to |--|-.

The ball leaves the array after $1$ second.

On the third change, the initial array is set to ---|-. This is the same as the first change, so the ball leaves the array after $7$ seconds.

On the fourth change, the initial array is set to -----, and all mirrors are horizontal. The ball leaves the array after $5$ seconds.