题目背景

Mivik 和 W!ʌ!k 在玩游戏！

题目描述

Mivik 首先把 $n$ 枚硬币摆成一排，其中有一些正面朝上，其余的都是反面朝上。W!ʌ!k 打算不断执行以下操作直到这 $n$ 枚硬币中没有硬币反面朝上：

• 如果现在这 $n$ 枚硬币中有 $k$ 枚硬币反面朝上，那么翻转从左到右第 $k$ 枚硬币。具体地，如果从左到右第 $k$ 枚硬币正面朝上，则将其变为反面朝上；如果从左到右第 $k$ 枚硬币反面朝上，则将其变为正面朝上。

在 W!ʌ!k 开始玩游戏之前，Mivik 想考考 W!ʌ!k。Mivik 想让 W!ʌ!k 算出他总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。

W!ʌ!k 很快解决了这个问题，但是心理比 yky 还变态的 Mivik 显然不会放过他。Mivik 进行了很多次操作，每次他翻转了一个区间的硬币，他要求 W!ʌ!k 算出他总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。

请注意，W!ʌ!k 只是需要计算总共会进行多少次操作，而不会真正进行操作。

输入格式

输入共 $\left(m+2\right)$ 行。

第一行为两个非负整数 $n,m$，其中 $n$ 表示 Mivik 的硬币的个数，$m$ 表示 Mivik 进行的翻转操作的次数。

第二行为一个只包含有 $\texttt H$ 和 $\texttt T$ 的字符串。第 $i$ 个字符 $s_i$ 为 $\texttt H$ 则表示从左到右第 $i$ 枚硬币初始时是正面朝上；$s_i$ 为 $\texttt T$ 则表示从左到右第 $i$ 枚硬币初始时是反面朝上。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，表示 Mivik 翻转了从左到右数 $l_i\sim r_i$（包括 $l_i$ 和 $r_i$）的硬币。

输出格式

输出 $\left(m+1\right)$ 行，分别表示在真正执行操作前后共 $\left(m+1\right)$ 个时刻开始 W!ʌ!k 总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。如果某一时刻 W!ʌ!k 不能停止执行操作，则在对应行输出字符串 $\texttt{never}$。

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

提示

样例解释 #1

初始时两枚硬币都是反面朝上，因此如果 W!ʌ!k 从此刻开始执行操作， W!ʌ!k 会将编号为 $2$ 的硬币翻转过来。操作后只有一枚硬币反面朝上，因此第 $2$ 次操作会将编号为 $1$ 的硬币翻转过来。在第 $2$ 次操作后没有硬币反面朝上，因此 W!ʌ!k 不会再执行操作，总共会执行 $2$ 次操作。

样例解释 #2

这 $8$ 次操作分别翻转了第 $2,1,2,3,4,3,2,1$ 枚硬币。

测试点约束

本题采用捆绑测试。

对于全部数据，有 $1\le n,m\le10^6$，$s_i\in\left\{\texttt H,\texttt T\right\}$，$1\le l_i\le r_i\le n$。

每个子任务的具体限制见下表：

本题读入输出量较大，请使用较快的读入输出方式。