codeforces#P1493E. Enormous XOR

    ID: 31867 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>bitmasksconstructive algorithmsgreedymathstringstwo pointers*2600

Enormous XOR

Description

You are given two integers $l$ and $r$ in binary representation. Let $g(x, y)$ be equal to the bitwise XOR of all integers from $x$ to $y$ inclusive (that is $x \oplus (x+1) \oplus \dots \oplus (y-1) \oplus y$). Let's define $f(l, r)$ as the maximum of all values of $g(x, y)$ satisfying $l \le x \le y \le r$.

Output $f(l, r)$.

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the binary representation of $r$.

The second line contains the binary representation of $l$ — a string of length $n$ consisting of digits $0$ and $1$ ($0 \le l < 2^n$).

The third line contains the binary representation of $r$ — a string of length $n$ consisting of digits $0$ and $1$ ($0 \le r < 2^n$).

It is guaranteed that $l \le r$. The binary representation of $r$ does not contain any extra leading zeros (if $r=0$, the binary representation of it consists of a single zero). The binary representation of $l$ is preceded with leading zeros so that its length is equal to $n$.

In a single line output the value of $f(l, r)$ for the given pair of $l$ and $r$ in binary representation without extra leading zeros.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the binary representation of $r$.

The second line contains the binary representation of $l$ — a string of length $n$ consisting of digits $0$ and $1$ ($0 \le l < 2^n$).

The third line contains the binary representation of $r$ — a string of length $n$ consisting of digits $0$ and $1$ ($0 \le r < 2^n$).

It is guaranteed that $l \le r$. The binary representation of $r$ does not contain any extra leading zeros (if $r=0$, the binary representation of it consists of a single zero). The binary representation of $l$ is preceded with leading zeros so that its length is equal to $n$.

Output

In a single line output the value of $f(l, r)$ for the given pair of $l$ and $r$ in binary representation without extra leading zeros.

Samples

7
0010011
1111010
1111111
4
1010
1101
1101

Note

In sample test case $l=19$, $r=122$. $f(x,y)$ is maximal and is equal to $127$, with $x=27$, $y=100$, for example.