abc子序列II

题目描述

Orange有一个字符串 $s$，他想知道 $s$ 中有多少个子序列为abc。 但是，这一次Orange有 $q$ 个询问，每次询问会给你一个闭区间 $[l,r]$，你需要将这个区间中的字符翻转过来，得到一个新的字符串 $s'$，Orange想知道每次询问的 $s'$ 中有多少个子序列为abc。

区间翻转的定义: $s_1 s_2 .. s_l s_{l+1} .. s_{r-1} s_r .. s_{n-1} s_n \rightarrow s_1 s_2 .. s_r s_{r-1} .. s_{l+1} s_l .. s_{n-1} s_n$. 例如abcabcabc,翻转$[4,6]$之后会变成abccbaabc。

子序列指的是从原字符串中删掉任意字符后，剩下的字符相对位置不变构成的新字符串，例如abbc的子序列有(a,b,c,ab,bc,bb,abc,abb,bbc,abbc…)，但是(ba,ca)不是。

输入格式

第一行包含两个整数 $n$ 和 $q(1 \le n,q \le 2 \times 10^5)$，表示字符串长度和询问次数。 第二行包含一个字符串 $s$。 随后 $q$ 行，每行两个整数 $l,r( 1\le l \le r \le n)$，表示该次询问翻转的区间。

输出格式

对于每个询问，给出答案。

样例 #1

样例输入 #1

6 2
aabbcc
2 3
1 6

样例输出 #1

6
0

提示

对于第一次询问，翻转后的字符串为ababcc,其中有6个abc子序列。 对于第二次询问，翻转后的字符串为ccbbaa,其中不存在abc子序列。