D. Задача со случайными тестами
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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)$$$.

Посчитайте максимальную стоимость, которую вы можете получить, и выведите ее в двоичной системе счисления без ведущих нулей.

Входные данные

В первой строке задано число $$$n$$$ — количество символов в $$$s$$$.

Во второй строке задана $$$s$$$, состоящая из ровно $$$n$$$ символов 0 и/или 1.

Все тесты в этой задаче, кроме примеров из условия, сгенерированы случайным образом: каждый символ $$$s$$$ выбирается независимо от остальных, и для каждого символа вероятность быть 1 равна $$$\frac{1}{2}$$$.

В этой задаче ровно $$$40$$$ тестов. Тесты с $$$1$$$ по $$$3$$$ — примеры из условия; тесты с $$$4$$$ по $$$40$$$ сгенерированы случайным образом. В тестах с $$$4$$$ по $$$10$$$ $$$n = 5$$$; в тестах с $$$11$$$ по $$$20$$$ $$$n = 1000$$$; в тестах с $$$21$$$ по $$$40$$$ $$$n = 10^6$$$.

В этой задаче запрещены взломы.

Выходные данные

Выведите максимальную стоимость, которую можно получить, в двоичной системе счисления без ведущих нулей.

Примеры
Входные данные
5
11010
Выходные данные
11111
Входные данные
7
1110010
Выходные данные
1111110
Входные данные
4
0000
Выходные данные
0
Примечание

В первом примере можно выбрать подстроки 11010 и 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, их побитовое ИЛИ равно $$$31$$$, а двоичное представление $$$31$$$ — это 11111.

Во втором примере можно выбрать подстроки 1110010 и 11100.