G - Binary Operation 解説 /

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

配点 : 650 点

問題文

A, B, C, D \in \lbrace 0, 1 \rbrace を満たす整数の組 (A, B, C, D) は 16 通りあります。それぞれに対して次の問題を解いてください。

0 と 1 からなる空でない文字列 S が次の条件を満たす時、S を美しい文字列と呼びます。

  • (条件) 次の一連の操作を S の長さが 1 になるまで行い、S に残った唯一の文字を 1 にすることができる。
    1. 1 \leq i \leq |S| - 1 を満たす整数 i を自由に選ぶ。
    2. 整数 x を次のように定義する。
      • S_i = 0 かつ S_{i+1}= 0 である場合、x = A とする。
      • S_i = 0 かつ S_{i+1}= 1 である場合、x = B とする。
      • S_i = 1 かつ S_{i+1}= 0 である場合、x = C とする。
      • S_i = 1 かつ S_{i+1}= 1 である場合、x = D とする。
    3. S_i と S_{i+1} を取り除き、それらがあった場所に x を数字とみなしたものを 1 個挿入する。
      例えば S= 10101 に対して i=2 を選んで操作を行った場合、操作後の文字列は B=0 の場合 1001 に、B=1 の場合 1101 になる。

0 と 1 からなる長さ N の文字列 T があります。

  • T の部分文字列である美しい文字列のうち最長のものの長さを L (ただし、T の部分文字列である美しい文字列が存在しない場合は L = -1 とする)、
  • T の部分文字列である美しい文字列の個数を M

とします。L および M を求めてください。ただし、2 つの部分文字列が文字列として同じでも、取り出す位置が異なるならば別々に数えます。

部分文字列とは S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、10 は 101 の部分文字列ですが、11 は 101 の部分文字列ではありません。

制約

  • 1 \leq N \leq 2 \times 10^5
  • N は整数
  • T は 0 と 1 からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
T

出力

16 行出力せよ。i 行目には i-1 = 8A + 4B + 2C + D を満たす (A,B,C,D) における L と M を空白区切りで出力せよ。

入力例 1

3
110

出力例 1

1 2
2 3
2 3
3 5
1 2
2 3
2 3
3 5
3 3
2 3
3 4
3 5
3 3
2 3
3 4
3 5

(A,B,C,D)=(0,0,0,1) の場合を説明します。
T の 1 文字目から 2 文字目までを取り出してできる文字列 11 は美しい文字列です。なぜならば、i=1 として操作を行うと、操作後の文字列は 1 になるからです。
(A,B,C,D)=(0,0,0,1) の場合、T の部分文字列である美しい文字列は次の 3 個です。

  • T の 1 文字目を取り出してできる文字列 1
  • T の 2 文字目を取り出してできる文字列 1
  • T の 1 文字目から 2 文字目までを取り出してできる文字列 11

入力例 2

4
0000

出力例 2

-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
4 4
4 4
4 6
4 6
4 6
4 6
4 6
4 6

入力例 3

30
011011100101110111100010011010

出力例 3

1 17
4 31
29 263
29 280
29 232
29 247
30 240
30 447
30 418
29 225
30 435
30 435
30 435
30 435
30 439
30 452

Score : 650 points

Problem Statement

There are 16 integer tuples (A, B, C, D) satisfying A, B, C, D \in \lbrace 0, 1 \rbrace. For each of them, solve the following problem.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

  • (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
    1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
    2. Define an integer x as follows:
      • If S_i = 0 and S_{i+1} = 0, let x = A.
      • If S_i = 0 and S_{i+1} = 1, let x = B.
      • If S_i = 1 and S_{i+1} = 0, let x = C.
      • If S_i = 1 and S_{i+1} = 1, let x = D.
    3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
      For example, if S= 10101 and you choose i=2, the string after the operation is 1001 if B=0, and 1101 if B=1.

You are given a string T of length N consisting of 0 and 1.

  • Let L be the length of the longest beautiful string that is a substring of T (if no substring of T is a beautiful string, let L = -1),
  • Let M be the number of beautiful strings that are substrings of T.

Find L and M. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings? A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • N is an integer.
  • T is a string of length N consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

N
T

Output

Print 16 lines. The i-th line should contain L and M separated by a space for (A,B,C,D) satisfying i-1 = 8A + 4B + 2C + D.

Sample Input 1

3
110

Sample Output 1

1 2
2 3
2 3
3 5
1 2
2 3
2 3
3 5
3 3
2 3
3 4
3 5
3 3
2 3
3 4
3 5

We explain the case (A,B,C,D)=(0,0,0,1).
The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1.
In the case (A,B,C,D)=(0,0,0,1), the beautiful strings that are substrings of T are the following three strings:

  • The string 1 obtained by taking the 1st character of T.
  • The string 1 obtained by taking the 2nd character of T.
  • The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
4 4
4 4
4 6
4 6
4 6
4 6
4 6
4 6

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

1 17
4 31
29 263
29 280
29 232
29 247
30 240
30 447
30 418
29 225
30 435
30 435
30 435
30 435
30 439
30 452