E. Enormous XORtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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).InputThe 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.OutputIn 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.ExamplesInput
7
0010011
1111010
Output
1111111Input
4
1010
1101
Output
1101
NoteIn sample test case l=19, r=122. f(x,y) is maximal and is equal to 127, with x=27, y=100, for example.
7
0010011
1111010

1111111
['bitmasks', 'constructive algorithms', 'greedy', 'math', 'strings', 'two pointers', '*2600']