Analyzing Bit (Yet Special) Strings

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 T1, T2, ..., Tn. Let's denote A(i, j) and B(i, j) as the number of 0-bits and 1-bits among Ti, Ti+1, ..., Tj, 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 L1 and L2 be the lengths of two strings, and P1 and P2 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 L1P1 > L2P2.

So your task is simple... or not? Find the best special string - a special string such that no other special string is better.


Only one line that contains the string S (2 ≤ |S| ≤ 2*105) consisting of zeroes and ones.


The first line should contain the value of LP, 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.

Time limit 3 seconds
Memory limit 256 MiB
Input example #1
Output example #1
Author Gennady Korotkevich
Source Gennady Korotkevich Contest 1, Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013