По данному натуральному числу n выведите все двоичные последовательности длины n, не содержащие двух единиц подряд, в лексикографическом порядке.

Входные данные

Одно натуральное число n (n ≤ 20).

Выходные данные

Вывести каждую последовательность в отдельной строке. Числа в последовательности следует разделять одним пробелом.