#include <iostream>
#include <vector>
#include <cmath>

std::vector<std::vector<int>> matrix;
//这里双重嵌套vector数组变为二维数组 类型为matrix

void solve(int r,int c,int n){
	if(n == 0){
		matrix[r][c] = 1;
		return;	//void函数没有返回值
	}
	int mid = 1 << (n-1);		//左移位 n-1把n阶砍一半
	//递归步骤：分为四个子方阵进行处理。
	//左上区域0 其余递归 左上区域依据规则已经全部初始化为0
	solve(r,c + mid,n - 1);
	solve(r+mid,c,n - 1);
	solve(r+mid,c+mid,n - 1);
}

int main(){
	std::ios_base::sync_with_stdio(false);		//关闭C++流与C标准I/O的同步。
	//为了保证cout和printf的输出顺序不错乱，cout在输出前需要等待printf，会增加很多额外的检查和等待时间。
	//但关闭同步后不能在代码中混用cin和printf或cout和scanf。
	std::cin.tie(NULL);	//解除cin和cout的绑定。告诉cin，你读你的，别再等cout再输出辣！
	
	int n;
	std::cin >> n;
	
	int size = 1 << n;
	matrix.assign(size,std::vector<int>(size,0));		//assign是std::vector库中的一个成员函数。是vector这个“工具”自带的一个功能。
	//作用为：清空一个vector的现有内容，然后用全新的内容来替代他们。嵌套内容要从内往外看。
	//void assign(size_type count,const T& value); count:新元素的个数 value:填充的值 vector会被填充count个value的拷贝
	//这还真的有点巧，括号里的size,std::vector<int>(size,0)可以看作一个向量
	//然后这里元素是向量，有size个向量线性组合，行和列齐了就变成了一个矩阵。
	
	solve(0,0,n);
	//从n阶矩阵的原点开始循环遍历每个点。这里在先前定义的solve函数里锁定了名字为matrix的二维数组。直接修改了main函数里存在的matrix。所以后期可以投射到输出里。
	
	for(int i = 0;i < size; ++i){
		for(int j = 0;j < size; ++j){
			std::cout << matrix[i][j];	//这里把矩阵里的0/1与输出结果一一对应。
			if(j <size - 1){
				std::cout << " ";	//每行非末元素空一格
			}
		}
		std::cout << "\n";	//行结束后换行
	}
	return 0;
}

void solve(std::vector<std::vector<int>>& blueprint,int r,int c,int n){
	if(n == 0){
        blueprint[r][c] = 1;
	    return;
	}
    //...
}

solve(matrix1,0,0,n);
solve(matrixx2,0,0,n);

std::cout << "Matrix1的结果" << std::endl;
// 循环打印for(i=0;i<matrix1.size;++i){略
std::cout << matrix1[i][j];

std::cout << "Matrix2的结果" << std::endl;
std::cout << matrix2[i][j];