CF1849C.Binary String Copying

You are given a string $s$ consisting of $n$ characters 0 and/or 1.

You make $m$ copies of this string, let the $i$-th copy be the string $t_i$. Then you perform exactly one operation on each of the copies: for the $i$-th copy, you sort its substring $[l_i; r_i]$ (the substring from the $l_i$-th character to the $r_i$-th character, both endpoints inclusive). Note that each operation affects only one copy, and each copy is affected by only one operation.

Your task is to calculate the number of different strings among $t_1, t_2, \ldots, t_m$. Note that the initial string $s$ should be counted only if at least one of the copies stays the same after the operation.

给你一个由 $n$ 个字符组成的字符串 $s$，其中每个字符为 0 或 1。

你将该字符串复制 $m$ 次，记第 $i$ 次复制得到的字符串为 $t_i$。然后，对每个副本恰好执行一次操作：对第 $i$ 个副本 $t_i$，将其子串 $[l_i; r_i]$（即从第 $l_i$ 个字符到第 $r_i$ 个字符的子串，包含两端）进行排序。注意，每次操作仅影响一个副本，且每个副本仅受一次操作影响。

你的任务是计算 $t_1, t_2, \ldots, t_m$ 中互不相同的字符串的个数。注意：初始字符串 $s$ 只有在至少有一个副本经过操作后保持不变时，才被计入答案。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of $s$ and the number of copies, respectively.

The second line contains $n$ characters 0 and/or 1 — the string $s$.

Then $m$ lines follow. The $i$-th of them contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the description of the operation applied to the $i$-th copy.

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$）—— 分别表示字符串 $s$ 的长度和副本数量。

第二行包含 $n$ 个字符，每个字符为 0 或 1 —— 即字符串 $s$。

接下来是 $m$ 行。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）—— 表示对第 $i$ 个副本执行的操作区间。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$；所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

Print one integer — the number of different strings among $t_1, t_2, \ldots, t_m$.

输出一个整数——即 $t_1, t_2, \ldots, t_m$ 中不同字符串的个数。

Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted:

1. 101100 $\rightarrow$ 011100;
2. 101100 $\rightarrow$ 011100;
3. 101100 $\rightarrow$ 101100;
4. 101100 $\rightarrow$ 101100;
5. 101100 $\rightarrow$ 000111.

There are three different strings among $t_1, t_2, t_3, t_4, t_5$: 000111, 011100 and 101100.

Consider the second example:

1. 100111 $\rightarrow$ 100111;
2. 100111 $\rightarrow$ 001111;
3. 100111 $\rightarrow$ 001111;
4. 100111 $\rightarrow$ 010111.

There are three different strings among $t_1, t_2, t_3, t_4$: 001111, 010111 and 100111.

考虑第一个例子。下方的字符串按输入操作的顺序给出。带下划线的子串是被排序的子串：

1. 101100 $\rightarrow$ 011100；
2. 101100 $\rightarrow$ 011100；
3. 101100 $\rightarrow$ 101100；
4. 101100 $\rightarrow$ 101100；
5. 101100 $\rightarrow$ 000111。

在 $t_1, t_2, t_3, t_4, t_5$ 中共有三个不同的字符串：000111、011100 和 101100。

考虑第二个例子：

1. 100111 $\rightarrow$ 100111；
2. 100111 $\rightarrow$ 001111；
3. 100111 $\rightarrow$ 001111；
4. 100111 $\rightarrow$ 010111。

在 $t_1, t_2, t_3, t_4$ 中共有三个不同的字符串：001111、010111 和 100111。