// Comment!
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define mp make_pair
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
const int maxn5 = 2e5 + 10;
vector <int> ns;
int h, w, lenh[maxn5], lenw[maxn5];
int isk(int st, int k, int n){
if(n - 1 < k)
return -1;
if(k == 0){
ns.clear();
for(int i = 0; i < n; i++)
ns.pb(i + st);
int cur = add_or(ns);
return add_not(cur);
}
//cout << "here " << st << ' ' << k << ' ' << n << endl;
ns.clear();
int st2 = -1;
int last = -1;
for(int i = 0; i + k < n; i++){
ns.clear();
ns = {i + st, i + k + st};
//cout << i + st << ' ' << i + k + st << ' ' << i << endl;
last = add_and(ns);
if(st2 == -1)
st2 = last;
}
//cout << "all here " << endl;
ns.clear();
for(int i = st2; i <= last; i++)
ns.pb(i);
return add_or(ns);
}
void construct_network(int H, int W, int k) {
h = H;
w = W;
if(min(h, w) > 1){
int sth = -1, last = -1;
for(int i = 0; i < h; i++){
ns.clear();
for(int j = 0; j < w; j++) if(i != 0 || j != 0)
ns.pb(i * w + j);
last = add_xor(ns);
if(sth == -1)
sth = last;
}
int stw = last + 1;
for(int j = 0; j < w; j++){
ns.clear();
for(int i = 0; i < h; i++) if(i != 0 || j != 0)
ns.pb(i * w + j);
last = add_xor(ns);
}
//cout << "done with h w" << endl;
int fr = -1;
last = -1;
for(int i = 0; i <= k; i++) if(i < h && k - i < w){
ns.clear();
ns = {sth + i, stw + k - i};
last = add_and(ns);
if(fr == -1)
fr = last;
}
ns.clear();
for(int i = fr; i <= last; i++)
ns.pb(i);
add_or(ns);
return;
}
int sth = -1, last = -1;
for(int i = 0; i < h; i++){
ns.clear();
for(int j = 0; j < w; j++)
ns.pb(i * w + j);
last = add_xor(ns);
if(sth == -1)
sth = last;
}
int stw = last + 1;
for(int j = 0; j < w; j++){
ns.clear();
for(int i = 0; i < h; i++)
ns.pb(i * w + j);
last = add_xor(ns);
}
memset(lenh, -1, sizeof lenh);
memset(lenw, -1, sizeof lenw);
for(int i = 0; i <= k; i++){
if(h - 1 >= i && w - 1 >= k - i)
lenh[i] = isk(sth, i, h);
if(w - 1 >= i && h - 1 >= k - i)
lenw[i] = isk(stw, i, w);
}
//cout << "done with h w" << endl;
int fr = -1;
last = -1;
for(int i = 0; i <= k; i++) if(lenh[i] != -1 && lenw[k - i] != -1){
ns.clear();
ns = {lenh[i], lenw[k - i]};
last = add_and(ns);
if(fr == -1)
fr = last;
}
ns.clear();
for(int i = fr; i <= last; i++)
ns.pb(i);
add_or(ns);
return;
}
