Analyzing Bit (Yet Special) Strings
Do you think that analyzing bit strings is easy? This is not the case when you are in a dream. So you are in a dream. Unexpectedly, right? But... I am afraid it's not the dream you always wanted to be in. You have a string of bits in your dream, a long string of bits you are to deal with. And you clearly understand what you should do to leave this horrible dream right now: find the best special string.
Luckily, you know that you read a book about the theory of special strings yesterday. You only managed to remember the strangest definition of special strings, though, which sounded as follows.
Suppose you have a string of bits T of length n. Bits of T are referred to as T_1, T_2, ..., T_n. Let's denote A(i, j) and B(i, j) as the number of 0-bits and 1-bits among T_i, T_{i+1}, ..., T_j, correspondingly. String T is called special if for every i between 1 and n, inclusive, both of the following conditions hold: A(1, i) ≥ B(1, i) and A(i, n) ≤ B(i, n).
But you can't be satisfied with just any special string. You need the best special string. The dream was very strange and thus the rules to determine which of two strings was better were strange as well. Let L_1 and L_2 be the lengths of two strings, and P_1 and P_2 be their numbers of occurrences in the given string S as a substring, respectively. Then you know that first string is better than the second one if L_1 ∙ P_1 > L_2 ∙ P_2.
So your task is simple... or not? Find the best special string - a special string such that no other special string is better.
Input
Only one line that contains the string S (2 ≤ |S| ≤ 2*10^5) consisting of zeroes and ones.
Output
The first line should contain the value of L ∙ P, where L is the length of the best special string and P is the number of its occurrences in S as a substring. The second line should contain the best special string itself. If there are several best special strings, you can choose any of them.
It is guaranteed that at least one special string is a substring of S.