CF1473D 程序

给定一个由 $n$ 条指令组成的程序。初始时，单个变量 $x$ 被赋值为 $0$ 。随后，指令有两种类型： - 将 $x$ 加 $1$； - 将 $x$ 减 $1$。 给定 $m$ 个如下格式的查询： - 查询 $l$ $r$ —— 如果忽略第 $l$ 条到第 $r$ 条（包含两端）之间的所有指令，按顺序执行其余指令，变量 $x$ 会被赋予多少个不同的值？

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$）—— 程序中指令的数量和查询的数量。 每个测试用例的第二行包含一个程序 —— 一个由 $n$ 个字符组成的字符串：每个字符要么是 `+` 要么是 `-`，分别表示加一和减一指令。 接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）—— 查询的描述。 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $m$ 个整数 —— 对于每个查询 $l$，$r$，输出忽略第 $l$ 条到第 $r$ 条（包含两端）之间的所有指令，按顺序执行其余指令时，变量 $x$ 被赋予的不同值的数量。

第一个测试用例中每个查询剩余的指令如下： 1. 空程序 —— $x$ 只等于 $0$； 2. `-` —— $x$ 的值为 $0$ 和 $-1$； 3. `---+` —— $x$ 的值为 $0$，$-1$，$-2$，$-3$，$-2$ —— 其中有 $4$ 个不同的值； 4. `+--+--+` —— 不同的值为 $1$，$0$，$-1$，$-2$ 。