题目描述

给定一段“+-”字符串序列 $s$ ，其中 $+$ 表示 $+1$, $-$ 表示 $−1$。

接下来，有 $q$ 次操作，假设每次的初始值是1,每次按顺序执行 $s_l...s_r$ 这一些列的指令，问你执行完这系列操作后的值是多少？

输入

每个测试用例的第一行包含两个整数 $n$ 和 $m$ （ $1 \le n, m \le 2 \cdot 10^5$ ）--程序指令数和查询次数。

每个测试用例的第二行包含一个程序--一个由 $n$ 个字符组成的字符串：每个字符要么是 "+"，要么是"-"分别是递增指令和递减指令。

接下来的每行 $m$ 包含两个整数 $l$ 和 $r$ ( $1 \le l \le r \le n$ ) , 表示执行指令的顺序。

输出

输出 $m$ 个整数 ，表示对于执行 $s_l...s_r$ 这一串指令后，最后的值是多少？

样例

输入样例

8 2
-+--+--+
1 2
1 3

输出样例

1
0

样例解释

• 对于第一次操作执行的指令是字符串$[s_1...s_2]$ 中的内容 :$-+$，因此他的值变化是 ${1,0,1}$ 最终输出为 $1$
• 对于第二次操作执行的指令是字符串$[s_1...s_3]$ 中的内容 :$-+-$，因此他的值变化是 ${1,0,1,0}$ 最终输出为 $0$