Program
Description
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?
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$.
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.
Input
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$.
Output
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.
Samples
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
2
4
4
3
3
4
2
3
2
1
2
2
2
Note
The instructions that remain for each query of the first testcase are:
- empty program — $x$ was only equal to $0$;
- "-" — $x$ had values $0$ and $-1$;
- "---+" — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them;
- "+--+--+" — the distinct values are $1$, $0$, $-1$, $-2$.