E - 11/22 Subsequence 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

この問題における 11/22 文字列の定義は A 問題および C 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

  • |T| は奇数である。ここで、|T| は T の長さを表す。
  • 1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
  • \frac{|T|+1}{2} 文字目が / である。
  • \frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられるので、Q 個のクエリを処理してください。

各クエリでは L, R が与えられます。S の L 文字目から R 文字目までからなる (連続な) 部分文字列を T としたとき、 11/22 文字列であるような T の (連続とは限らない) 部分列の長さの最大値を求めてください。そのような部分列が存在しないときは 0 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S は 1, 2, / からなる長さ N の文字列
  • 1 \leq L \leq R \leq N
  • N, Q, L, R は整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

L R

出力

Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。

入力例 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

出力例 1

5
0
3
1
7

1 番目のクエリについて、S の 1 文字目から 7 文字目からなる部分文字列は 111/212 です。この文字列は 11/22 を部分列として含み、これは 11/22 文字列であるような部分列として最大です。よって答えは 5 です。
2 番目のクエリについて、S の 9 文字目から 12 文字目からなる部分文字列は 1122 です。この文字列は 11/22 文字列であるような部分列を含まないので、答えは 0 です。

Score : 500 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and C.

A string T is called an 11/22 string when it satisfies all of the following conditions:

  • |T| is odd. Here, |T| denotes the length of T.
  • The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
  • The (\frac{|T|+1}{2})-th character is /.
  • The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, process Q queries.

Each query provides two integers L and R. Let T be the (contiguous) substring of S from the L-th through R-th character. Find the maximum length of a subsequence (not necessarily contiguous) of T that is an 11/22 string. If no such subsequence exists, print 0.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S is a string of length N consisting of 1, 2, and /.
  • 1 \leq L \leq R \leq N
  • N, Q, L, and R are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i denotes the i-th query.

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

L R

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

Sample Output 1

5
0
3
1
7

For the first query, the substring from the 1-st to 7-th character of S is 111/212. This string contains 11/22 as a subsequence, which is the longest subsequence that is an 11/22 string. Therefore, the answer is 5.
For the second query, the substring from the 9-th to 12-th character of S is 1122. This string does not contain any subsequence that is an 11/22 string, so the answer is 0.