给定一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$。 $$$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$$$。
此问题禁止黑客攻击。
输出
以二进制表示形式打印不带前导零的最大可能值。
示例
输入 #1
5 11010
输出 #1
11111
输入 #2
7 1110010
输出 #2
1111110
输入 #3
4 0000
输出 #3
0
注意
在第一个示例中,您可以选择子字符串 11010 和 101。$$$f(s_1) = 26$$$,$$$f(s_2) = 5$$$,它们的按位或为 $$$31$$$,$$$31$$$ 的二进制表示为 11111。
在第二个示例中,您可以选择子字符串 1110010 和 11100。