Program

题目描述

给你一个有 $n$ 条指令的程序，指令仅为 $+$ 或 $-$ ：

• $+$ 即 $x$ 的值增加 $1$ ；
• $-$ 即 $x$ 的值减少 $1$ 。

有 $m$ 条命令，对于每条命令：

• 询问除区间 $[ l , r ]$ 内的所有指令外其余的指令按顺序执行，求执行指令的过程中 $x$ 出现了多少种值。

输入格式

第 $1$ 行输入一个正整数 $t$ ( $1 \le t \le 1000$ )——样例的数量。

在每个样例中：

第 $1$ 行有两个整数 $n$ 和 $m$ ( $1 \le n, m \le 2 \cdot 10^5$ )—— $n$ 是指令的个数， $m$ 是询问的个数（如题目描述）。

第 $2$ 行有 $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$ 获得的不同值的数量