Description

You are given a string $s$ of length $n$ consisting of characters $\texttt{v}$, $\texttt{a}$, and $\texttt{n}$. Let $s_i$ denote the $i$-th character of $s$.

Little O will perform $m$ operations. In each operation, you are given an integer $x$ ($1 \le x \le n-1$), requiring you to swap $s_x$ and $s_{x+1}$.

After each operation, output the number of times $\texttt{van}$ appears as a subsequence in the modified string.

• A string $t$ is a subsequence of $s$ if it can be obtained by deleting zero or more characters from $s$ without changing the order of the remaining characters.

Input Format

The input consists of $m+2$ lines:

• Line $1$: Two integers $n$ and $m$, the string length and number of operations.
• Line $2$: A string $s$ of length $n$.
• Lines $3$ to $m+2$: Each line contains an integer $x_i$, representing the $i$-th operation.

Output Format

Output $m$ lines, where the $i$-th line contains the answer after the $i$-th operation.

8 3
vvvaannn
4
3
5

18
15
12

Hint

Sample #1 Explanation

Initial State: $s = \texttt{vvvaannn}$

• After swapping positions $4$ and $5$: $s$ remains unchanged. $\texttt{van}$ appears 18 times.
• After swapping positions $3$ and $4$: $s = \texttt{vvavannn}$. $\texttt{van}$ appears 15 times.
• After swapping positions $5$ and $6$: $s = \texttt{vvavnann}$. $\texttt{van}$ appears 12 times.

Constraints

• $3 \le n \le 10^6$, $1 \le m \le 10^6$
• $s_i \in \{\texttt{v}, \texttt{a}, \texttt{n}\}$

Subtask Details

Special Property A: In all swap operations, at least one of $s_x$ or $s_{x+1}$ is $\texttt{a}$.