题目描述

给你一个包含$\red{n}$个指令的程序，最开始$\red{x}$的值为$\red{0}$。接下来，每一个指令都在这两种类型之间：

$\red{-：}$$\red{x}$减一；

$\red{+：}$$\red{x}$加一。

我们设$\red{F(S)}$表示执行当前操作序列过程中出现过的不同的数的数量（包括开始时的$\red{0）}$。

现在有$\red{m}$组询问，每次询问给定一段区间$\red{[l,r]，}$你需要回答忽略这段操作序列后，求整个序列的$\red{F}$值。

输入格式

第一行输入两个整数$\red{n,m，}$表示指令的个数和询问的个数。

第二行一个仅包含$\red{+}$和$\red{-}$的长度为$\red{n}$的字符串，表示指令串。

接下来$\red{m}$行，每行两个整数$\red{l,r，}$表示一组询问。

输出格式

对于每个询问输出一行一个整数，表示忽略这段操作序列后，执行当前操作序列过程中出现过的不同的 数的数量。

样例

输入样例

8 4
-+--+--+
1 8
2 8
2 5
1 1

输出样例

1
2
4
4

提示

对于$\red{50\%}$的数据，$\red{1<=n,m<=10^3}$。

对于$\red{100\%}$的数据，$\red{a<=n,m<=2\times 10^5,1<=l<=r<=n}$。