AT_abc418_g [ABC418G] Binary Operation

$ 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` の部分文字列ではありません。

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

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

### Sample Explanation 1 $ (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` ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ N $ は整数 - $ T $ は `0` と `1` からなる長さ $ N $ の文字列