测试数据来自 nnu_contest/1236

F.奇怪的程序(Hard)

时间限制：2~5秒
(不卡常数)
空间限制：512MB

题目背景

本题的Hard版本与Medium版本唯一的区别在于：本版本中可能出现第三种字符*。

你得到了一份奇怪的代码。

根据说明文档，这份代码只由三种字符构成。程序开始时将自动定义一个初值为0的整型变量X。三个字符和相对应的作用是：

'+'，将X增加1。

'-'，将X减少1。

'*', 将X增加3。

题目描述

现有m个询问，每个询问给出两个正整数\(l\le r\)

问：仅保留程序的第[l,r]个字符，程序在运行过程中，变量X会取到多少种不同的取值？

初始化的赋值不计算在内

输入格式

第一行包括两个整数\(n,m\)，分别表示程序的长度和询问的个数。

第二行包括一个长度为\(n\)的字符串，字符串中仅包含提到的三种字符。

之后的\(m\)行每行包含两个正整数\(1\le l\le r\le n\)

输出格式

共\(m\)行，每行一个整数表示答案。

数据范围及限制

\(n,m\le 10^6\)

样例输入

3 3
-**
1 2
1 3
2 3

样例输出

2
3
2

样例解释

对于第一次询问，x的值分别为:-1，2。一共有两个不同的值。
对于第二次询问，x的值分别为:-1，2，5。一共有三个不同的值。
对于最后一次询问，x的值分别为:3，6。一共有两个不同的值。