Дана строка \(s\) из \(n\) символов. Каждый символ \(s\) — либо 0, либо 1.
Подстрока строки \(s\) — это непрерывная подпоследовательность ее символов.
Вы должны выбрать две подстроки \(s\) (возможно, пересекающиеся, возможно, одну и ту же два раза, возможно, непересекающиеся — две любые подстроки). После того как вы выбрали подстроки, вы считаете их стоимость следующим образом:
- пусть \(s_1\) — первая подстрока, \(s_2\) — вторая подстрока, а \(f(s_i)\) — целое число, для которого \(s_i\) является записью в двоичной системе счисления (напримре, если \(s_i\) — это 11010, то \(f(s_i) = 26\));
- стоимость пары подстрок — это побитовое ИЛИ чисел \(f(s_1)\) и \(f(s_2)\).
Посчитайте максимальную стоимость, которую вы можете получить, и выведите ее в двоичной системе счисления без ведущих нулей.
Выходные данные
Выведите максимальную стоимость, которую можно получить, в двоичной системе счисления без ведущих нулей.
Примечание
В первом примере можно выбрать подстроки 11010 и 101. \(f(s_1) = 26\), \(f(s_2) = 5\), их побитовое ИЛИ равно \(31\), а двоичное представление \(31\) — это 11111.
Во втором примере можно выбрать подстроки 1110010 и 11100.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
11010
|
11111
|
|
2
|
7
1110010
|
1111110
|
|
3
|
4
0000
|
0
|