题目描述

有一个奇幻的矩阵，在不停的变幻，其变幻方式为：
数字 1 变成矩阵

1 1
1 2

数字 2 变成矩阵

2 2
2 1

最初该矩阵只有一个元素 1，变幻 n 次后，矩阵会变成什么样？
例如，矩阵最初为：[1]；

矩阵变幻 1 次后：

1 1 
1 2

矩阵变幻 2 次后：

1 1 1 1
1 2 1 2
1 1 2 2
1 2 2 1

输入格式

一行一个整数 n，表示矩阵变幻的次数

输出格式

输出若干行，每行若干个整数，整数间以空格分开，表示变幻 n 次后的矩阵

样例 #1

样例输入 #1

3

样例输出 #1

1 1 1 1
1 2 1 2
1 1 2 2
1 2 2 1