#include "vision.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 40'010;
int h, w, k;
int n;
int nxt;
int get_n(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w? x*w + y: -1;}
void ha(int a, int b, int &x, int &y)
{
// a^b a&b
add_xor({a, b});
add_and({a, b});
x = nxt;
y = nxt+1;
nxt += 2;
}
void fa(int a, int b, int c, int &x, int &y)
{
// a^b a^b^c a&b (a^b)&c (a&b)|((a^b)&c)
add_xor({a, b});
add_xor({nxt, c});
add_and({a, b});
add_and({nxt, c});
add_or({nxt+2, nxt+3});
x = nxt+1;
y = nxt+4;
nxt += 5;
}
void byte_add(int a[], int b[], int x[])
{
int c[9];
ha(a[0], b[0], x[0], c[0]);
Loop (i,1,9)
fa(a[i], b[i], c[i-1], x[i], c[i]);
}
void byte_write(int val, int x[])
{
Loop (i,0,9) {
add_xor({n+(val&1)});
x[i] = nxt++;
val >>= 1;
}
}
void byte_cmp(int a[], int b[], int &x)
{
Loop (i,0,9)
add_xor({a[i], b[i]});
add_or({nxt+0, nxt+1, nxt+2, nxt+3, nxt+4, nxt+5, nxt+6, nxt+7, nxt+8});
add_not(nxt+9);
x = nxt+9;
nxt += 11;
}
void construct_network(int H, int W, int K)
{
h = H; w = W; k = K;
n = w*h;
add_xor({0,0});
add_not(n);
nxt = n+2;
int A[9], B[9];
int dis[9], goal[9];
Loop (dir,0,2) {
int kooft = nxt;
Loop (j,0,(dir?h:w)) {
vector<int> vec;
Loop (i,0,(dir?w:h))
vec.push_back(get_n(dir?j:i, dir?i:j));
add_xor(vec);
nxt++;
}
Loop (bit,0,9) {
int marg = nxt;
Loop (off,0,(1<<bit)) {
vector<int> vec;
Loop (j,0,dir?h:w) {
if ((j+off) & (1<<bit))
vec.push_back(kooft+j);
}
vec.size()? add_xor(vec): add_xor({n});
++nxt;
}
vector<int> vec;
Loop (i,marg,nxt)
vec.push_back(i);
add_and(vec);
(dir?B:A)[bit] = nxt++;
}
}
byte_add(A, B, dis);
byte_write(k, goal);
int ans;
byte_cmp(dis, goal, ans);
//printf("a = %d\nb = %d\nsum = %d\nk = %d\n", n+2, n+11, dis, goal);
}
