Código de Gray (Gray code)

O código de Gray (Gray code) de comprimento n é a lista de todas as sequências de bits de tamanho n que diferem exatamente num bit (ou seja, cuja distância de Hamming é 1).

Dado um inteiro n, pretende-se imprimir o código de Gray em linhas.

Entrada

A entrada contém um único inteiro n (1 ≤ n ≤ 16).

Saída

O programa deve imprimir o código de Gray. Qualquer solução válida é aceitável.

Exemplos