В известной на всю страну Весенней компьютерной школе скоро начнется новая смена, и в связи с этим весь дружный состав преподавателей и кураторов начал составлять ее расписание. В процессе обсуждения они пришли к расписанию \(s\), которое может быть представлено в виде бинарной строки, в которой на \(i\)-й позиции стоит «1», если ученики в \(i\)-й день пишут контест, и «0», если отдыхают.
В последний момент на заседание пришел Глеб и заявил, что если смена в школе проходит по расписанию \(t\) (которое может быть описано в таком же формате, что и \(s\)), то ученики особенно хорошо усваивают материал. Поскольку количество дней в грядущей смене может отличаться от количества дней в \(t\), Глеб потребовал, чтобы уже составленное расписание переделали таким образом, чтобы количество вхождений \(t\) в него как подстроки было максимально. При этом количество учебных и выходных дней не должно измениться, может измениться только порядок их следования.
Сможете ли вы переставить порядок дней в расписании оптимальным образом?
Выходные данные
В единственной строке выведите расписание, количество вхождений \(t\) как подстроки в которое максимально. Выведенное расписание должно состоять только из «0» и «1», причём количество нулей должно совпадать с количеством нулей в \(s\), а количество единиц — с количеством единиц в \(s\).
Если существует несколько оптимальных расписаний, выведите любое из них.
Примечание
В первом примере два вхождения, начинающихся с первой и четвертой позиции.
Во втором примере всего одно вхождение, и оно начинается с третьей позиции. Заметим также, что ответ не единственен — например, самый первый день (являющийся выходным) можно переместить на последнюю позицию, и кол-во вхождений \(t\) не изменится.
В третьем примере добиться даже одного вхождения не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
101101
110
|
110110
|
|
2
|
10010110
100011
|
01100011
|
|
3
|
10
11100
|
01
|