#include <bits/stdc++.h>
#include "vision.h"
#pragma GCC optimize("O3")
using namespace std;
int ab(int a, int b, int W){
int x = a/W, X = b/W, y = a%W, Y = b%W;
if(x > X) swap(x, X);
if(y > Y) swap(y, Y);
return X-x+Y-y;
}
void st1(int H, int W, int K){
vector<int> dx(min(K,H-1)+1), dy(min(K,W-1)+1);
vector<int> xr;
for(int i = 0; i < H; i++){
vector<int> x;
for(int j = 0; j < W; j++) x.push_back(i*W+j);
xr.push_back(add_xor(x));
xr.back() = add_not(xr.back());
}
dx[0] = add_and(xr);
xr.clear();
for(int j = 0; j < W; j++){
vector<int> x;
for(int i = 0; i < H; i++) x.push_back(i*W+j);
xr.push_back(add_xor(x));
xr.back() = add_not(xr.back());
}
dy[0] = add_and(xr);
for(int x = 1; x <= min(K,H-1); x++){
vector<int> ask_f;
for(int i = 0; i < H-x; i++){
vector<int> ask;
for(int j = 0; j < W; j++) ask.push_back(i*W+j);
int t1 = add_or(ask);
ask.clear();
for(int j = 0; j < W; j++) ask.push_back((i+x)*W+j);
int t2 = add_or(ask);
ask_f.push_back(add_and({t1, t2}));
}
dx[x] = add_or(ask_f);
}
for(int x = 1; x <= min(K,W-1); x++){
vector<int> ask_f;
for(int j = 0; j < W-x; j++){
vector<int> ask;
for(int i = 0; i < H; i++) ask.push_back(i*W+j);
int t1 = add_or(ask);
ask.clear();
for(int i = 0; i < H; i++) ask.push_back(i*W+j+x);
int t2 = add_or(ask);
ask_f.push_back(add_and({t1, t2}));
}
dy[x] = add_or(ask_f);
}
vector<int> fin;
for(int i = 0; i <= min(K,H-1); i++){
if(K-i > W-1) continue;
fin.push_back(add_and({dx[i], dy[K-i]}));
}
add_or(fin);
}
void st6(int H, int W, int K){
int c = 0;
for(int i = 1; i < H*W; i++)
if(ab(0, i, W) == K) add_and({i}), c++;
vector<int> x;
for(int i = H*W; i < H*W+c; i++) x.push_back(i);
add_or(x);
}
void st7(int H, int W){
int t1, t2;
vector<int> f_ask;
for(int i = 0; i < H-1; i++){
vector<int> x, y;
for(int j = 0; j < W; j++)
x.push_back(i*W+j),
y.push_back((i+1)*W+j);
int ind1 = add_or(x), ind2 = add_or(y);
f_ask.push_back(add_and({ind1, ind2}));
}
int tmp1 = add_or(f_ask), tmp2;
f_ask.clear();
for(int j = 0; j < W; j++){
vector<int> x;
for(int i = 0; i < H; i++) x.push_back(i*W+j);
f_ask.push_back(add_xor(x));
}
tmp2 = add_or(f_ask);
tmp2 = add_not(tmp2);
t1 = add_and({tmp1, tmp2});
f_ask.clear();
for(int j = 0; j < W-1; j++){
vector<int> x, y;
for(int i = 0; i < H; i++)
x.push_back(i*W+j),
y.push_back(i*W+j+1);
int ind1 = add_or(x), ind2 = add_or(y);
f_ask.push_back(add_and({ind1, ind2}));
}
tmp1 = add_or(f_ask);
f_ask.clear();
for(int i = 0; i < H; i++){
vector<int> x;
for(int j = 0; j < W; j++) x.push_back(i*W+j);
f_ask.push_back(add_xor(x));
}
tmp2 = add_or(f_ask);
tmp2 = add_not(tmp2);
t2 = add_and({tmp1, tmp2});
add_or({t1, t2});
}
void construct_network(int H, int W, int K) {
if((H <= 30 && W <= 30) || (H == 1 || W == 1)) st1(H, W, K);
else if(K == 1) st7(H, W);
else st6(H, W, K);
}
