#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int lim=210;
int pref1[lim],pref2[lim];
int p1(int l,int r){
if(!l)return pref1[r];
return add_xor({pref1[r],pref1[l-1]});
}
int p2(int l,int r){
if(!l)return pref2[r];
return add_xor({pref2[r],pref2[l-1]});
}
struct {
int tree[4*lim];
int P,VAL;
int N;
void init(int n){
N=n;
}
void update(int l,int r,int node){
if(l==r){
tree[node]=VAL;
return;
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
}
void update(int p,int val) {
P=p,VAL=val;
update(0,N-1,1);
}
int build(int l,int r,int node){
if(l==r){
return tree[node];
}
int mid=(l+r)>>1,child=node<<1;
return tree[node]=add_or({build(l,mid,child),build(mid+1,r,child|1)});
}
void build(){
build(0,N-1,1);
}
vector<int>need;
int L,R;
void query(int l,int r,int node){
if(L<=l&&r<=R){
need.pb(tree[node]);
return;
}
if(r<L||R<l)return;
int mid=(l+r)>>1,child=node<<1;
query(l,mid,child),query(mid+1,r,child|1);
}
int query(int l,int r){
L=l,R=r;
need.clear();
query(0,N-1,1);
return add_or(need);
}
}st1,st2;
void construct_network(int H, int W, int K) {
#define tr(x,y) ((x)*W+(y))
#define check(x,y) (0<=(x)&&(x)<H&&0<=(y)&&(y)<W)
vector<int>sat1,sat2,sat3;
int cnt1=0,cnt2=0;
unordered_map<int,vector<int>>wc,nc;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
wc[i+j].pb(tr(i,j));
nc[i-j].pb(tr(i,j));
}
}
unordered_map<int,int>r1,r2;
for(int i=-1000;i<1000;i++){
if(wc.count(i)){
r1[i]=add_or(wc[i]);
if(r1.count(i-K)){
sat1.pb(add_and({r1[i],r1[i-K]})),cnt1++;
}
}
if(nc.count(i)){
r2[i]=add_or(nc[i]);
if(r2.count(i-K)){
sat1.pb(add_and({r2[i],r2[i-K]})),cnt2++;
}
}
}
int xor1[H],or1[H];
st1.init(H);
for(int i=0;i<H;i++){
vector<int>th;
for(int j=0;j<W;j++){
th.pb(tr(i,j));
}
xor1[i]=add_xor(th);
if(i)pref1[i]=add_xor({xor1[i],pref1[i-1]});
else pref1[i]=xor1[i];
or1[i]=add_or(th);
st1.update(i,or1[i]);
}
int xor2[W],or2[W];
st2.init(W);
for(int i=0;i<W;i++){
vector<int>th;
for(int j=0;j<H;j++){
th.pb(tr(j,i));
}
xor2[i]=add_xor(th);
if(i)pref2[i]=add_xor({xor2[i],pref2[i-1]});
else pref2[i]=xor2[i];
or2[i]=add_or(th);
st2.update(i,or2[i]);
}
st1.build(),st2.build();
for(int i=0;i<H;i++){
int haveblack=st1.query(i,min(i+K,H-1));
int haveboth=p1(i,min(i+K,H-1));
sat2.pb(add_and({haveblack,add_not(haveboth)}));
}
for(int i=0;i<W;i++){
int haveblack=st2.query(i,min(i+K,W-1));
int haveboth=p2(i,min(i+K,W-1));
sat3.pb(add_and({haveblack,add_not(haveboth)}));
}
//ending
add_and({add_or(sat1),add_or(sat2),add_or(sat3)});
}
/*
void construct_network(int H, int W, int K) {
std::vector<int> Ns;
Ns = {0, 1};
int a = add_and(Ns);
Ns = {0, a};
int b = add_or(Ns);
Ns = {0, 1, b};
int c = add_xor(Ns);
add_not(c);
}
*/
