Аналізуючи бітові (ще й спеціальні) рядки
Ви думаєте, що аналізувати рядки просто? Це так, але лише якщо Ви не у ві сні. Але Ви спите і Вам сниться сон. Несподівано, правда ж? Але... я боюсь, що це не сон, у якому Ви хотіли б опинитись. У Вашому сні є рдок бітів, довгий рядок бітів, з яким Вам доведеться мати справу. І Ви чітко розумієте, що потрібно зробити, щоб залишити цей жахливий сон прямо зараз: необхідно знайти кращий спеціальний рядок.
На щастя, Ви учора прочитали книжку по теорії спеціальних рядків. Вам вдалось лише згадати дивне визначення спеціальних рядків, яке виглядало наступним чином.
Нехай у Вас є рядок бітів T довжини n. Біти T позначимо через T_1, T_2, ..., T_n. Позначимо через A(i, j) та B(i, j) кількість 0-бітів та 1-бітів серед T_i, T_{i+1}, ..., T_{j }відповідно. Рядок T називається спеціальним, якщо для кожного i між 1 та n включно має місце наступне співвідношення: A(1, i) ≥ B(1, i) та A(i, n) ≤ B(i, n).
Проте Вас не задовольняє будь-який спеціальний рядок. Вам потрібен найкращий спеціальний рядок. Сон був занадто дивним, тому і правило, яке визначає, який з рядків кращий, також виглядає дуже дивним. Нехай L_1 та L_2 - довжини двох рядків, а P_1 та P_2 - кількість разів, які вони зустрічаються у вхідному рядку S у якості підрядків відповідно. Перший рядок вважається кращим другого, якщо L_1∙P_1 > L_2∙P_2.
Отже, Ваша задача проста... чи ні? Знайдіть найкращий спеціальний рядок - такий спеціальний рядок, що жоден з інших спеціальних рядків не кращий нього.
Вхідні дані
Один рядок S (2 ≤ |S| ≤ 2*10^5), який складається з нулів та одиниць.
Вихідні дані
Перший рядок повинен містити значення L∙P, де L - довжина найкращого спеціального рядка, а P - число його входжень у S в якості підрядка. Другий рядок повинен містити сам найкращий рядок. Якщо таких є декілька, то виведіть довільний.
Гарантується, що як мінімум один спеціальний рядок є підрядоком S.