#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
#define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
#define cerr cout
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
#include "vision.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings
const int INF = 1e9;
const ll INFL = 1e18;
const int N = 1e5;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
#define ENC(i,j) ((i) * m + (j))
void construct_network(int n, int m, int dist) {
vi diag1(n+m), diag2(n+m);
for (int i = 0; i < n + m; i++) {
vi pos;
for (int j = 0; j <= i; j++) {
int row = j, col = i - j;
if (0 <= row && row < n && 0 <= col && col < m) {
pos.push_back(ENC(row, col));
}
}
diag1[i] = pos.empty() ? -1 : add_or(pos);
}
for (int d = 0; d < n+m; d++) {
vi pos;
for (int i = 0, j = d - n; i < n && j < m; i++, j++) {
if (j >= 0) {
pos.push_back(ENC(i, j));
}
}
diag2[d] = pos.empty() ? -1 : add_or(pos);
}
vi eq, gt;
for (int i = 0; i + dist < sz(diag1); i++) {
if (diag1[i] != -1 && diag1[i+dist] != -1) {
eq.push_back(add_and({diag1[i], diag1[i+dist]}));
}
if (diag2[i] != -1 && diag2[i+dist] != -1) {
eq.push_back(add_and({diag2[i], diag2[i+dist]}));
}
}
for (int i = 0; i < sz(diag1); i++) {
vi cur1, cur2;
for (int j = i + dist + 2; j < sz(diag1); j += 2) {
if (diag1[i] != -1 && diag1[j] != -1)
cur1.push_back(diag1[j]);
if (diag2[i] != -1 && diag2[j] != -1)
cur2.push_back(diag2[j]);
}
if (!cur1.empty()) gt.push_back(add_and({diag1[i], add_or(cur1)}));
if (!cur2.empty()) gt.push_back(add_and({diag2[i], add_or(cur2)}));
}
if (!gt.empty())
add_and({add_or(eq), add_not(add_or(gt))});
else
add_or(eq);
return;
}
#undef ENC
