AT_abc418_g [ABC418G] Binary Operation

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`.

The input is given from Standard Input in the following format: > $ N $ $ T $

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 Explanation 1 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 $ . ### 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`.