#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;
#include "prison.h"
struct stu{
int tp , xr , bg ;
};
stu app[ 70 ] ;
int pos[ 30 ][ 30 ] ;
vector<vector<int>> devise_strategy(int N){
int xx[ 10 ] ;
xx[ 0 ] = 1 ;
for( int j = 1 ; j <= 7 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 3 ;
int cur = 1 , tt = 1 ;
for( int j = 0 ; j <= 7 ; j ++ ){
stu a ; a.tp = 0 ; a.xr = j ; a.bg = tt ;
app[ cur ] = a ; a.tp = 1 ;
app[ cur + 1 ] = a ; a.tp = 2 ;
app[ cur + 2 ] = a ;
pos[ 0 ][ j ] = cur ;
pos[ 1 ][ j ] = cur + 1 ;
pos[ 2 ][ j ] = cur + 2 ;
tt = ( tt + 1 ) % 2 ;
cur += 3 ;
}
// 0 --> A , 1 --> B
vector < int > v ;
vector < vector < int > > ans ;
v.pb( 0 ) ;
int st = 7 ;
for( int j = 1 ; j <= N ; j ++ ){
// now get which type is this number for the st
int x = j ;
int cc = 0 ;
if( x >= xx[ st ] ){
cc ++ ;
x -= xx[ st ] ;
}
if( x >= xx[ st ] ){
cc ++ ;
x -= xx[ st ] ;
}
v.pb( pos[ cc ][ st ] ) ;
}
ans.pb( v ) ;
for( int j = 1 ; j < cur ; j ++ ){
v.clear() ;
stu axl = app[ j ] ;
if( axl.bg == 1 ) v.pb( 1 ) ;
else v.pb( 0 ) ;
int ss = axl.xr ;
int cc = axl.tp ;
for( int nmb = 1 ; nmb <= N ; nmb ++ ){
int x = nmb ;
for( int k = 7 ; k > ss ; k -- ){
if( x >= xx[ k ] ) x -= xx[ k ] ;
if( x >= xx[ k ] ) x -= xx[ k ] ;
}
int cnt = 0;
if( x >= xx[ ss ] ) cnt ++ , x-= xx[ ss ] ;
if( x >= xx[ ss ] ) cnt ++ , x-= xx[ ss ] ;
if( cnt < cc ){
if( axl.bg == 1 ) v.pb( -2 ) ;
else v.pb( -1 ) ;
continue ;
}
if( cnt > cc ){
if( axl.bg == 1 ) v.pb( -1 ) ;
else v.pb( -2 ) ;
continue ;
}
int xixo = 0 ;
if( x >= xx[ ss - 1 ] ) xixo ++ , x-= xx[ ss - 1 ] ;
if( x >= xx[ ss - 1 ] ) xixo ++ , x-= xx[ ss - 1 ] ;
v.pb( pos[ xixo ][ ss - 1 ] ) ;
}
ans.pb( v ) ;
}
return ans ;
}
// static constexpr int kNumPrisoners = 500;
// static void invalid_strategy(std::string message) {
// printf("%s\n", message.c_str());
// exit(0);
// }
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<std::vector<int>> strategy = devise_strategy(N);
// if (strategy.size() == 0) {
// invalid_strategy("s is an empty array");
// }
// int x = strategy.size() - 1;
// for (int i = 0; i <= x; ++i) {
// if (static_cast<int>(strategy[i].size()) != N + 1) {
// invalid_strategy("s[i] contains incorrect length");
// }
// if (strategy[i][0] < 0 || strategy[i][0] > 1) {
// invalid_strategy("First element of s[i] is non-binary");
// }
// for (int j = 1; j <= N; ++j) {
// if (strategy[i][j] < -2 || strategy[i][j] > x) {
// invalid_strategy("s[i][j] contains incorrect value");
// }
// }
// }
// FILE *log_file = fopen("log.txt","w");
// int A, B;
// while (1 == scanf("%d", &A) && A != -1) {
// assert(1 == scanf("%d", &B));
// bool answer = false;
// int whiteboard = 0;
// for (int i = 0; i < kNumPrisoners && !answer; ++i) {
// int check = strategy[whiteboard][0];
// whiteboard = strategy[whiteboard][check == 0 ? A : B];
// if (whiteboard < 0) {
// answer = true;
// printf("%c\n", "BA"[whiteboard + 2]);
// } else {
// if (i > 0) {
// fprintf(log_file, " ");
// }
// fprintf(log_file, "%d", whiteboard);
// }
// }
// if (!answer) {
// printf("X\n");
// }
// fprintf(log_file, "\n");
// fflush(log_file);
// }
// }
