# 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 **T _{1}**,

**T**, ...,

_{2}**T**. Let's denote

_{n}**A**(

**i**,

**j**) and

**B**(

**i**,

**j**) as the number of

**0**-bits and

**1**-bits among

**T**,

_{i}**T**, ...,

_{i+1}**T**, correspondingly. String

_{j}**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**be the lengths of two strings, and

_{2}**P**and

_{1}**P**be their numbers of occurrences in the given string

_{2}**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**.

00111001110101

8 0011