## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Problem with Random Tests Codeforces Solution

D. Problem with Random Tests
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $s$ consisting of $n$ characters. Each character of $s$ is either 0 or 1.

A substring of $s$ is a contiguous subsequence of its characters.

You have to choose two substrings of $s$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:

• let ${s}_{1}$ be the first substring, ${s}_{2}$ be the second chosen substring, and $f\left({s}_{i}\right)$ be the integer such that ${s}_{i}$ is its binary representation (for example, if ${s}_{i}$ is 11010$f\left({s}_{i}\right)=26$);
• the value is the bitwise OR of $f\left({s}_{1}\right)$ and $f\left({s}_{2}\right)$.

Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.

Input

The first line contains one integer $n$ — the number of characters in $s$.

The second line contains $s$ itself, consisting of exactly $n$ characters 0 and/or 1.

All non-example tests in this problem are generated randomly: every character of $s$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $\frac{1}{2}$.

This problem has exactly $40$ tests. Tests from $1$ to $3$ are the examples; tests from $4$ to $40$ are generated randomly. In tests from $4$ to $10$$n=5$; in tests from $11$ to $20$$n=1000$; in tests from $21$ to $40$$n={10}^{6}$.

Solution Click Below:-  👉
👇👇👇👇👇

Hacks are forbidden in this problem.

Output

Print the maximum possible value you can get in binary representation without leading zeroes.

Note

In the first example, you can choose the substrings 11010 and 101$f\left({s}_{1}\right)=26$$f\left({s}_{2}\right)=5$, their bitwise OR is $31$, and the binary representation of $31$ is 11111.

In the second example, you can choose the substrings 1110010 and 11100.