给你一个由 $$$n$$$ 指令组成的程序。最初,单个变量 $$$x$$$ 被分配给 $$$0$$$。之后,指令有两种类型:
- 将 $$$x$$$ 增加 $$$1$$$;
- 将 $$$x$$$ 减少 $$$1$$$。
您将收到以下格式的 $$$m$$$ 查询:
- 查询 $$$l$$$ $$$r$$$ — 如果忽略第 $$$l$$$ 和第 $$$r$$$ 之间的所有指令,而执行其余指令而不更改顺序,则 $$$x$$$ 会分配多少个不同的值?
输入
第一行包含一个整数 $$$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$$$ 之间的所有指令,并且执行其余指令而不更改顺序。
示例
输入 #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. 空程序——$$$x$$$ 只等于$$$0$$$;
2. “-”— $$$x$$$ 的值为 $$$0$$$ 和 $$$-1$$$;
3. "---+" — $$$x$$$ 的值为 $$$0$$$、$$$-1$$$、$$$-2$$$、$$$-3$$$、$$$-2$$$ — 其中有 $$$4$$$ 不同的值;
4.“+--+--+”— 不同的值为 $$$1$$$、$$$0$$$、$$$-1$$$、$$$-2$$$。