Задана программа, состоящая из \(n\) инструкций. Изначально единственная переменная \(x\) присваивается \(0\). После этого следуют инструкции двух типов:
Даны \(m\) запросов следующего типа:
В первой строке записано одно целое число \(t\) (\(1 \le t \le 1000\)) — количество наборов входных данных.
Затем следует описание \(t\) наборов входных данных.
В первой строке каждого набора входных данных записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 2 \cdot 10^5\)) — количество инструкций в программе и количество запросов.
Во второй строке каждого набора входных данных записана программа — последовательность из \(n\) символов: каждый символ равен либо '+', либо '-' — инструкция увеличения и уменьшения, соответственно.
В каждой из следующих \(m\) строк записаны по два целых числа \(l\) и \(r\) (\(1 \le l \le r \le n\)) — описание запроса.
Сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\). Сумма \(m\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
На каждый набор входных данных выведите \(m\) целых чисел — для каждого запроса \(l\), \(r\) выведите количество различных значений, которые принимает переменная \(x\), если все инструкции между \(l\)-й и \(r\)-й включительно пропускаются, а остальные исполняются без изменения порядка.
Инструкции, которые остаются в каждом запросе первого набора входных данных:
2 8 4 -+--+--+ 1 8 2 8 2 5 1 1 4 10 +-++ 1 1 1 2 2 2 1 3 2 3 3 3 1 4 2 4 3 4 4 4
1 2 4 4 3 3 4 2 3 2 1 2 2 2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач