#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "vision.h"
void construct_network(int H, int W, int K) {
VVI left, right;
int dsize = H+W-1;
left = right = VVI(dsize);
rep(i, H) rep(j, W) {
left[j-i+H-1].pb(i*W + j);
right[i+j].pb(i*W + j);
}
int start = H*W;
auto addgate1 = [&](VVI side) {
int d[4];
// d[0] or
// d[1] xor
// d[2] not xor
// d[3] (not xor) and (or)
d[0] = start;
d[1] = d[0] + dsize;
d[2] = d[1] + dsize;
d[3] = d[2] + dsize;
rep(i, dsize) {
add_or(side[i]);
}
rep(i, dsize) {
add_xor(side[i]);
}
rep(i, dsize) {
add_not(d[1] + i);
}
rep(i, dsize) {
add_and({d[2]+i, d[0]+i});
}
start = d[3] + dsize;
return PII{d[0], d[3]};
};
auto addgate2 = [&](int L, int dor) {
int groupsize = dsize-L+1;
int group[4];
// group[0] or
// group[1] xor
// group[2] not xor
// group[3] (not xor) and (or)
group[0] = start;
group[1] = group[0] + groupsize;
group[2] = group[1] + groupsize;
group[3] = group[2] + groupsize;
rep(i, groupsize) {
VI tmp;
replr(j, i, i+L-1) tmp.pb(dor+j);
add_or(tmp);
}
rep(i, groupsize) {
VI tmp;
replr(j, i, i+L-1) tmp.pb(dor+j);
add_xor(tmp);
}
rep(i, groupsize) {
add_not(group[1] + i);
}
rep(i, groupsize) {
add_and({group[0] + i, group[2] + i});
}
start = group[3] + groupsize;
return group[3];
};
auto[d1or, d1both] = addgate1(left);
auto[d2or, d2both] = addgate1(right);
auto addgate3 = [&](int L) {
int d1group = addgate2(L, d1or);
int d2group = addgate2(L, d2or);
VI tmp;
tmp = VI();
replr(i, d1both, d1both + dsize-1) tmp.pb(i);
replr(i, d1group, d1group + (dsize-L+1) - 1) tmp.pb(i);
add_or(tmp);
start++;
tmp = VI();
replr(i, d2both, d2both + dsize-1) tmp.pb(i);
replr(i, d2group, d2group + (dsize-L+1) - 1) tmp.pb(i);
add_or(tmp);
start++;
add_and({start-1, start-2});
return start++;
};
int g1 = addgate3(K+1); // must be true
int g2 = addgate3(K); // must be false
int g2not = add_not(g2);
add_and({g1, g2not});
}
/*
* add_not
* add_and
* add_or
* add_xor
*/
