程序

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 条指令组成的程序。变量 $x$ 的初始值为 $0$；字符 + 表示把 $x$ 加一，字符 - 表示把 $x$ 减一。

每次查询给出区间 $[l,r]$。删去这个区间内的全部指令后，按原顺序执行其余指令。请回答执行过程中（包括尚未执行任何指令时）变量 $x$ 一共取到多少个不同的整数值。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含两个整数 $n,m$；第二行包含一个长度为 $n$、仅由 + 和 - 组成的字符串；接下来 $m$ 行每行包含两个整数 $l,r$。

输出格式

对每个查询输出一行答案。

样例输入 1

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

1
2
4
4
3
3
4
2
3
2
1
2
2
2

数据范围

对于全部数据，$1\le t\le1000$，$1\le n,m\le2\times10^5$，$1\le l\le r\le n$；单个输入中所有测试用例的 $n$ 之和不超过 $2\times10^5$，$m$ 之和也不超过 $2\times10^5$。