Problem Background

Mivik and W!ʌ!k are playing a game!

Problem Description

Mivik starts by arranging \( n \) coins in a row, with some facing heads up and the rest tails up. W!ʌ!k plans to repeatedly perform the following operation until there are no coins facing tails up:

• If there are \( k \) coins facing tails up among the \( n \) coins, flip the \( k \)-th coin from the left. Specifically, if the \( k \)-th coin from the left is heads up, change it to tails up; if it is tails up, change it to heads up.

Before W!ʌ!k starts playing, Mivik wants to test W!ʌ!k. Mivik wants W!ʌ!k to calculate the total number of such operations he will perform, or whether W!ʌ!k will never stop performing operations.

W!ʌ!k quickly solved this problem, but Mivik, who is even more twisted in mind than yky, obviously won't let him off easily. Mivik performs many operations, each time flipping a range of coins, and he demands W!ʌ!k to calculate the total number of such operations, or whether W!ʌ!k will never stop performing operations.

Note that W!ʌ!k only needs to calculate the total number of operations and will not actually perform the operations.

Input Format

The input consists of \( (m+2) \) lines.

The first line contains two non-negative integers \( n \) and \( m \), where \( n \) represents the number of coins Mivik has, and \( m \) represents the number of flip operations Mivik performs.

The second line is a string containing only 'H' and 'T'. The \( i \)-th character \( s_i \) being 'H' indicates that the \( i \)-th coin from the left is initially heads up; \( s_i \) being 'T' indicates that the \( i \)-th coin from the left is initially tails up.

The next \( m \) lines, each containing two positive integers \( l_i \) and \( r_i \), indicate that Mivik flips the coins numbered \( l_i \) to \( r_i \) (including \( l_i \) and \( r_i \)) from the left.

Output Format

Output \( (m+1) \) lines, each indicating the total number of operations W!ʌ!k would perform starting from the \( (m+1) \) moments before and after the actual operations, or that W!ʌ!k will never stop performing operations. If at any moment W!ʌ!k cannot stop performing operations, output the string "never" on the corresponding line.

Sample Input and Output

Sample Input #1

2 2
TT
2 2
1 2

Sample Output #1

2
1
3

Sample Input #2

5 0
HTHTH

Sample Output #2

8

Sample Input #3

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

Sample Output #3

19
30
27
40
33
38
27
28
37
40
47

Notes

Sample Explanation #1

Initially, both coins are tails up, so if W!ʌ!k starts performing operations from this moment, he will flip the coin numbered 2. After the operation, only one coin is tails up, so the second operation will flip the coin numbered 1. After the second operation, there are no coins tails up, so W!ʌ!k will not perform any more operations, totaling 2 operations.

Sample Explanation #2

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

Test Case Constraints

This problem uses subtask testing.

For all data, \( 1 \le n, m \le 10^6 \), \( s_i \in \{\texttt{H}, \texttt{T}\} \), \( 1 \le l_i \le r_i \le n \).

The specific restrictions for each subtask are as follows:

This problem has a large input/output size, please use fast input/output methods.

见题面 Input 部分

见题面 Output 部分