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.
• Choose any integer $i$ satisfying $1 \leq i \leq |S| - 1$.
  • 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$.
  • 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$.