#include "Anna.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace {
vector<pii> dir = {{-1e9,-1e9},{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
map<pii,int> Index = {{{-1,-1},0},{{-1,0},1},{{-1,1},2},{{0,-1},3},{{0,0},4},{{0,1},5},{{1,-1},6},{{1,0},7},{{1,1},8}};
}
void Anna(int n, int K, vi A, vi B)
{
vector<vector<int>> ans(n, vector<int>(n, 12));
vector<pii> base_pos = {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
int movex = 0;
int movey = 0;
rep(i,3)
{
rep(j,3)
{
bool is_ok = true;
rep(k,K)
{
if((base_pos[k].ff+i+2)%3 == A[k] % 3 && (base_pos[k].ss + j+2)%3 == B[k] % 3)
{
is_ok = false;
}
}
if(is_ok)
{
movex = j;
movey = i;
}
}
}
rep(i,9)
{
base_pos[i].ff += movey;
base_pos[i].ss += movex;
base_pos[i].ff %= 3;
base_pos[i].ss %= 3;
}
vector<bool> was_used(9,0);
rep(i,K)
{
rep2(j,1,9)
{
pii it = dir[j];
if(it.ff == -1e9) continue;
if((A[i]+it.ff)%3 == base_pos[i].ff && (B[i]+it.ss)%3 == base_pos[i].ss)
{
was_used[j] = 1;
break;
}
}
}
int un_used = 0;
rep2(i,1,8) if(was_used[i] == 0) un_used = i;
rep(i,n)
{
rep(j,n)
{
int poz = 0;
rep(k,9)
{
if(i%3 == base_pos[k].ff && j%3 == base_pos[k].ss)
{
poz = k;
}
}
if(poz == 7)
{
ans[i][j] = un_used;
}
else if(poz == 8)
{
ans[i][j] = 12;
}
else
{
int a = -1;
rep2(k,1,9)
{
pii it = dir[k];
if((i-it.ff) == A[poz] && (j-it.ss) == B[poz])
{
a = k;
break;
}
}
if(a != -1)
{
if(a > un_used) a--;
ans[i][j] = a;
}
else
{
int disty = A[poz]-i;
int distx = B[poz]-j;
if(abs(distx) > abs(disty))
{
if(distx > 0)
{
ans[i][j] = 9;
}
else
{
ans[i][j] = 11;
}
}
else
{
if(disty > 0)
{
ans[i][j] = 10;
}
else
{
ans[i][j] = 8;
}
}
}
}
}
}
rep(i,n) rep(j,n) SetFlag(i,j,ans[i][j]);
}
#include "Bruno.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace {
vector<pii> dir = {{-1e9,-1e9},{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
map<pii,int> Index = {{{-1,-1},0},{{-1,0},1},{{-1,1},2},{{0,-1},3},{{0,0},4},{{0,1},5},{{1,-1},6},{{1,0},7},{{1,1},8}};
}
vi Bruno(int k, vi A)
{
vector<pii> base_pos = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
vector<pii> base_pos2 = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
vi ans(k);
int movex = 0;
int movey = 0;
rep(y,3)
{
rep(x,3)
{
int p = y*3+x;
if(A[p] == 12)
{
movex = (2-x);
movey = (2-y);
}
}
}
rep(i,9)
{
base_pos[i].ff = (base_pos[i].ff - movey+6) % 3;
base_pos[i].ss = (base_pos[i].ss - movex+6) % 3;
if(base_pos[i].ff == 2) base_pos[i].ff = -1;
if(base_pos[i].ss == 2) base_pos[i].ss = -1;
}
int un_used = A[Index[base_pos[7]]];
rep(k,7)
{
int w = A[Index[base_pos[k]]];
switch(w)
{
case 8:
{
ans[k] = 3;
break;
}
case 9:
{
ans[k] = 0;
break;
}
case 10:
{
ans[k] = 2;
break;
}
case 11:
{
ans[k] = 1;
break;
}
default:
{
if(w < 8)
{
if(w >= un_used) w++;
}
int pozy = 0 + base_pos[k].ff - base_pos2[w-1].ff;
int pozx = 0 + base_pos[k].ss - base_pos2[w-1].ss;
if(pozy == 0)
{
if(pozx > 0)
{
ans[k] = 0;
}
else if(pozx < 0)
{
ans[k] = 1;
}
else
{
ans[k] = 4;
}
}
else
{
if(pozy > 0)
{
ans[k] = 2;
}
else
{
ans[k] = 3;
}
}
}
}
}
return ans;
}
