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

Задана программа, состоящая из $$$n$$$ инструкций. Изначально единственная переменная $$$x$$$ присваивается $$$0$$$. После этого следуют инструкции двух типов:

  • увеличить $$$x$$$ на $$$1$$$;
  • уменьшить $$$x$$$ на $$$1$$$.

Даны $$$m$$$ запросов следующего типа:

  • запрос $$$l$$$ $$$r$$$ — сколько различных значений принимает переменная $$$x$$$, если все инструкции между $$$l$$$-й и $$$r$$$-й включительно пропускаются, а остальные исполняются без изменения порядка?
Входные данные

В первой строке записано одно целое число $$$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
Примечание

Инструкции, которые остаются в каждом запросе первого набора входных данных:

  1. пустая программа — $$$x$$$ был равен только $$$0$$$;
  2. «-» — $$$x$$$ принимал значения $$$0$$$ и $$$-1$$$;
  3. «---+» — $$$x$$$ принимал значения $$$0$$$, $$$-1$$$, $$$-2$$$, $$$-3$$$, $$$-2$$$ — среди них $$$4$$$ различных значения;
  4. «+--+--+» — различные значения — это $$$1$$$, $$$0$$$, $$$-1$$$, $$$-2$$$.