Серебрянная матрица

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

1. Размеры матрицы n×n.

2. Все элементы матрицы лежат во множестве S = {1, 2, 3, …, 2n-1}.

3. Для каждого целого числа i (1 ≤ i ≤ n), все элементы i-ой строки и i-го столбца образуют множество {1, 2, 3, …, 2n-1}.

Например, следующая матрица размера 4×4 является серебрянной:

Доказано, что серебрянная матрица размером 2^K×2^K всегда существует. Вам следует построить серебрянную матрицу 2^K×2^K.

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

Единственное число K (1 ≤ K ≤ 9).

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

Вывести серебрянную матрицу размером 2^K×2^K. Для вывода матрицы 2^K×2^K, следует вывести 2^K строки, каждая из которых содержит 2^K целых чисел.

Примеры