34243번 - 힝스티비와 쿼리

문제

덧셈, 뺄셈, XOR을 공부하던 나도리는 각 연산자를 나열하다가 표정 문자열이라는 것을 만들었다. 표정 문자열은 +, -, ^ 으로만 이루어진 문자열이다.+^+은 뭔가 신나 보이는 표정이고, -^-은 뭔가 힝스러운 표정이다.

표정 문자열의 흥미도는 문자열에 존재하는 아래 부분 문자열의 개수에 따라 정해진다.

• +^+: 1ドル$점
• -^-: $-1$점

표정 문자열을 만든 후, 월간 향유회 멤버들은 표정 문자열을 이용하여 매일 아침에 운세를 보기 시작했다.

1ドル \leq \ell \leq r \leq \left\vert S \right\vert$을 만족하는 두 정수 $\ell,ドル $r$을 고르면, 나도리는 표정 문자열 $S[\ell:r]$의 흥미도를 알려 준다. $S[\ell:r]$은 $S$의 $\ell$번째 문자부터 $r$번째 문자까지로 구성된 부분 문자열이다.

힝스한 표정이 너무 많으면 아침부터 기분도 힝스해지기 때문에 나도리는 기특한 생각을 하나 해 냈다.

$S[\ell:r]$에서 최대 하나의 문자를 지운 상태에서 흥미도의 최대를 알려 주자!

$Q$개의 운세 요청이 들어왔을 때 나도리가 적절한 운세를 볼 수 있게 해 주자.

입력

첫째 줄에 표정 문자열 $S$가 주어진다. (1ドル \leq \left\vert S \right\vert \leq 300,000円$)

둘째 줄에 쿼리의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 300,000円$)

셋째 줄부터 $Q$줄에 걸쳐 구간을 나타내는 두 정수 $\ell,ドル $r$이 공백으로 구분되어 주어진다. (1ドル \leq \ell \leq r \leq \left\vert S \right\vert$)

출력

쿼리마다 $S[\ell:r]$에서 최대 하나의 문자를 지운 상태에서 흥미도의 최댓값을 한 줄에 출력한다.

제한

힌트