Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Копирование бинарной строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$s$$$, состоящая из $$$n$$$ символов 0 и/или 1.

Вы делаете $$$m$$$ копий этой строки. Пусть $$$i$$$-я копия — это строка $$$t_i$$$. Затем вы выполняете ровно одну операцию над каждой из копий: в $$$i$$$-й копии вы сортируете подстроку $$$[l_i; r_i]$$$ (подстроку, начинающуюся с $$$l_i$$$-го символа и заканчивающуюся $$$r_i$$$-м символом, обе границы включаются). Заметьте, что каждая операция затрагивает только одну копию, и каждая копия затрагивается только одной операцией.

Ваша задача — посчитать количество различных строк среди $$$t_1, t_2, \ldots, t_m$$$. Заметьте, что изначальная строка $$$s$$$ должна считаться только тогда, когда хотя бы одна копия остается неизменной после операции.

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Выведите одно целое число — количество различных строк среди $$$t_1, t_2, \ldots, t_m$$$.

Пример
Входные данные
3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1
Выходные данные
3
3
1
Примечание

Рассмотрим первый тестовый пример. Копии ниже представлены в порядке операций из входных данных. Сортируемые подстроки подчеркнуты:

  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.