グレイコード

長さ n のグレイコードとは、ビット列の長さが n のすべての列について、互いにちょうど1ビットだけ異なる（ハミング距離が1となる）ように並べたリストのことです。

整数 n が与えられたとき、 行のグレイコードを出力してください。

入力

入力は単一の整数 n (1 ≤ n ≤ 16) を含みます。

出力

プログラムはグレイコードを出力してください。どのような生成方法でも構いません。

例