Generate Binary Strings Without Consecutive Ones

Given an integer \(N\), generate all possible binary strings of length \(N\) that do not contain consecutive 1s. A binary string is a sequence composed solely of the characters '0' and '1'. The string must not contain the substring 11. The output should be in lexicographical (sorted) order.

Example:

Input: 3
Output:
000
001
010
100
101

Note: The input will be provided from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The input consists of a single integer \(N\) on a single line, where \(N \geq 0\). This integer represents the length of the binary string to generate.

outputFormat

Output all valid binary strings, each on a new line, in lexicographical order. Each binary string should be of length \(N\) and must not contain consecutive 1s.

## sample

1

0
1

</p>