Binary Traversal String Generation

Given a non‐negative integer \( n \), generate a binary traversal string of length \(2^{n}\). This string is constructed such that every possible binary substring of length \( n \) appears exactly once as a contiguous segment. For \( n = 0 \), output should be 0; for \( n = 1 \), output 01 is expected (although 10 is also correct), for \( n \ge 2 \>, the output is derived from a de Bruijn sequence.

Note: A de Bruijn sequence for alphabet size 2 and subsequences of length \( n \) is a cyclic sequence in which every possible string of length \( n \) appears exactly once. In our problem, we output a linear sequence by taking the first \(2^{n}\) digits of the generated de Bruijn sequence.

inputFormat

The input consists of a single non-negative integer \( n \) provided via standard input. \( n \) represents the order of binary substrings to be traversed.

outputFormat

Output a single string of length \(2^{n}\) representing the binary traversal sequence generated as described above. The result is printed to standard output.

0

0