CF1473D.Program

You are given a program that consists of $n$ instructions. Initially a single variable $x$ is assigned to $0$. Afterwards, the instructions are of two types:

• increase $x$ by $1$;
• decrease $x$ by $1$.

You are given $m$ queries of the following format:

• query $l$ $r$ — how many distinct values is $x$ assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order?

你被给定一个包含 $n$ 条指令的程序。初始时，单个变量 $x$ 被赋值为 $0$。随后，指令分为两种类型：

• 将 $x$ 的值增加 $1$；
• 将 $x$ 的值减少 $1$。

你将收到 $m$ 个如下格式的查询：

• 查询 $l$ $r$ —— 若忽略第 $l$ 条至第 $r$ 条（含）之间的所有指令，而其余指令按原顺序执行，则 $x$ 在整个执行过程中总共取过多少个不同的值？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Then the description of $t$ testcases follows.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of instructions in the program and the number of queries.

The second line of each testcase contains a program — a string of $n$ characters: each character is either '+' or '-' — increment and decrement instruction, respectively.

Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the query.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each testcase print $m$ integers — for each query $l$, $r$ print the number of distinct values variable $x$ is assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order.

对于每个测试用例，输出 $m$ 个整数——对每个查询 $l, r$，输出在忽略第 $l$ 条至第 $r$ 条（含）指令、其余指令保持原有顺序执行的情况下，变量 $x$ 被赋值的不同值的个数。

The instructions that remain for each query of the first testcase are:

1. empty program — $x$ was only equal to $0$;
2. "-" — $x$ had values $0$ and $-1$;
3. "---+" — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them;
4. "+--+--+" — the distinct values are $1$, $0$, $-1$, $-2$.

第一个测试用例中，每个查询所剩余的指令如下：

1. 空程序 — $x$ 的值仅等于 $0$；
2. "-" — $x$ 的值依次为 $0$ 和 $-1$；
3. "---+" — $x$ 的值依次为 $0$、$-1$、$-2$、$-3$、$-2$ — 其中包含 $4$ 个不同的值；
4. "+--+--+" — 不同的值为 $1$、$0$、$-1$、$-2$。