Luo Gu Pardon prisoners of war

Background

With the help of anti cheating system , Some players who had plagiarized and cheated in the monthly competition were caught ！

Title Description

existing  2^n*2^n(n≤10)  A cheater stood in a square array and waited kkksc03 Hair fall .kkksc03 Pardon some cheaters . He divided the square matrix into 4 A smaller square matrix , The side length of each smaller matrix is half of the original matrix . All cheaters in the upper left matrix will be pardoned , be left over 3 In a small matrix , Each matrix continues to be divided into 4 A smaller matrix , Then pardon the cheater in the same way …… Until the matrix can no longer be divided . All cheaters who are not pardoned will be punished by Brown name .

give  n, Please output the fate of each cheater , among 0 The representative was pardoned ,1 Means not to be pardoned .

Input format

An integer  nn.

Output format

2^n*2^n Of 01 matrix , Represents whether everyone is pardoned . There is a space between the numbers .

I/o sample

Input #1 Copy

3

Output #1 Copy

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

#include<bits/stdc++.h>  
using namespace std;
const int N=1024+1;  //2 The tenth power of is 1024, We are violent from the beginning , So we have to add one .
int n;
int a[N][N];  // Set the size of the matrix .

int main()
{
    scanf("%d",&n);
    int maxn=1;
    for(int i=1;i<=n;i++)  // Find the size of the matrix .
      maxn*=2;
    for(int j=1;j<=maxn;j++)  // Set the last column to 1.
      a[j][maxn]=1;
    /*
	 Binary addition is like this ：
	0+0=0  1+0=1  0+1=1  1+1=0
	 The sum of the two addends equals 1, Then its result is 1, It is 0.
	*/ 
    for(int i=2;i<=maxn;i++)  // Be careful i from 2 Start , Because the first line except the last one is 1, Everything else is 0
     for(int j=1;j<=maxn;j++) 
       if(a[i-1][j]+a[i-1][j+1]==1)  a[i][j]=1;  // The result of this value is equal to a[i-1][j]+a[i-1][j+1]
       else  a[i][j]=0;
    for(int i=1;i<=maxn;i++)  // Finally, the output matrix .
    {
      for(int j=1;j<=maxn;j++)
        printf("%d ",a[i][j]);
      printf("\n");
    }
    return 0;
}