Description

Mivik first places $n$ coins in a row. Some are face up and the rest are face down. W!ʌ!k plans to repeatedly perform the following operation until none of the $n$ coins is face down:

• If there are currently $k$ coins that are face down among the $n$ coins, then flip the $k$-th coin from left to right. Specifically, if the $k$-th coin from left to right is face up, change it to face down; if it is face down, change it to face up.

Before W!ʌ!k starts playing, Mivik wants to test W!ʌ!k. Mivik wants W!ʌ!k to compute how many such operations he will perform in total, or whether W!ʌ!k will never be able to stop performing operations.

W!ʌ!k solved this problem quickly, but Mivik, whose mindset is even more twisted than yky's, obviously would not let him off. Mivik performs many flips: each time, he flips an interval of coins, and he requires W!ʌ!k to compute how many such operations W!ʌ!k will perform in total, or whether W!ʌ!k will never be able to stop performing operations.

Note that W!ʌ!k only needs to compute how many operations will be performed in total, and will not actually perform the operations.

Input Format

The input has $\left(m+2\right)$ lines.

The first line contains two non-negative integers $n,m$, where $n$ is the number of Mivik's coins, and $m$ is the number of interval-flip operations performed by Mivik.

The second line is a string consisting only of $\texttt H$ and $\texttt T$. If the $i$-th character $s_i$ is $\texttt H$, it means the $i$-th coin from left to right is initially face up; if $s_i$ is $\texttt T$, it means the $i$-th coin from left to right is initially face down.

The next $m$ lines each contain two positive integers $l_i,r_i$, meaning Mivik flipped the coins from positions $l_i$ to $r_i$ (inclusive) from left to right.

Output Format

Output $\left(m+1\right)$ lines. They represent, at the $\left(m+1\right)$ moments (before actually performing any of Mivik's flips, and after each of the $m$ flips), how many such operations W!ʌ!k would perform in total if he starts at that moment, or whether W!ʌ!k will never be able to stop performing operations. If at some moment W!ʌ!k cannot stop performing operations, output the string $\texttt{never}$ on the corresponding line.

2 2
TT
2 2
1 2

2
1
3

5 0
HTHTH

8

10 10
HTHHTHTHHH
9 9
5 5
10 10
7 7
6 6
9 9
4 4
9 9
7 7
2 2

19
30
27
40
33
38
27
28
37
40
47

Hint

Sample Explanation #1

Initially, both coins are face down, so if W!ʌ!k starts performing operations from this moment, he will flip coin $2$. After that, only one coin is face down, so the second operation will flip coin $1$. After the second operation, no coin is face down, so W!ʌ!k will not perform any more operations, and he will perform $2$ operations in total.

Sample Explanation #2

These $8$ operations flip coins $2,1,2,3,4,3,2,1$, respectively.

Test Point Constraints

This problem uses bundled tests.

For all data, $1\le n,m\le10^6$, $s_i\in\left\{\texttt H,\texttt T\right\}$, $1\le l_i\le r_i\le n$.

The specific limits for each subtask are shown in the table below:

The input and output size of this problem is large, so please use fast I/O.

Translated by ChatGPT 5