#include "vision.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i,a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 410;
int get_xor(int *x, int l, int r) {
if(l == 0) return x[r];
return add_xor({x[r], x[l - 1]});
}
vector<vector<int>> dia1; // x + y, [0, H + W - 2]
vector<vector<int>> dia2; // x - y + W - 1, [0, H + W - 2]
int xor1[MAXN], xor2[MAXN];
int check(int k) {
int n = sz(dia1);
vector<int> v;
For(i, 0, n - k - 1) {
vector<int> q;
For(j, 0, k) q.insert(q.end(), all(dia1[i + j]));
// or = 1, xor = 0 => 2 black cells
v.eb(add_xor({add_or(q), get_xor(xor1, i, i + k)}));
}
int a = add_or(v);
v.clear();
For(i, 0, n - k - 1) {
vector<int> q;
For(j, 0, k) q.insert(q.end(), all(dia2[i + j]));
// or = 1, xor = 0 => 2 black cells
v.eb(add_xor({add_or(q), get_xor(xor2, i, i + k)}));
}
int b = add_or(v);
return add_and({a, b});
}
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);
int n = H + W - 1;
dia1.resize(n);
dia2.resize(n);
For(i, 0, H - 1) For(j, 0, W - 1) {
int id = i * W + j;
dia1[i + j].eb(id);
dia2[i - j + W - 1].eb(id);
}
xor1[0] = add_xor(dia1[0]);
xor2[0] = add_xor(dia2[0]);
For(i, 1, n - 1) {
dia1[i].eb(xor1[i - 1]);
xor1[i] = add_xor(dia1[i]);
dia1[i].pop_back();
dia2[i].eb(xor2[i - 1]);
xor2[i] = add_xor(dia2[i]);
dia2[i].pop_back();
}
int a = check(K);
int b = check(K - 1);
b = add_not(b);
add_and({a, b});
}
