#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, BITS = 9;
struct State {
int bits[BITS], inc; };
int rows[N], cols[N];
int ZERO, ONE;
static vector<int> make_op(int a, int b) {
return (vector<int> {a, b}); }
static State make_state(int k = 0) {
State res;
if (k == 0) {
for (int i = 0; i < BITS; ++i)
res.bits[i] = ZERO;
res.inc = ZERO; }
else {
for (int i = 0; i < BITS; ++i)
res.bits[i] = (((1 << i) & k) ? ONE : ZERO);
res.inc = ZERO; }
return res; }
static State inc_if(State arg, int cond) {
State res;
int rem = cond;
for (int i = 0; i < BITS; ++i) {
res.bits[i] = add_xor(make_op(rem, arg.bits[i]));
rem = add_and(make_op(rem, arg.bits[i]));
if (i + 1 == BITS)
break; }
res.inc = cond;
return res; }
static State add(State a, State b) {
State ans;
int rem = ZERO;
for (int i = 0; i < BITS; ++i) {
ans.bits[i] = add_xor(vector<int> {a.bits[i], b.bits[i], rem});
rem = add_and(vector<int>{
add_or({rem, a.bits[i]}),
add_or({a.bits[i], b.bits[i]}),
add_or({b.bits[i], rem}),
});
}
ans.inc = ZERO;
return ans; }
static int different(State a, State b) {
int acc = ZERO;
for (int i = 0; i < BITS; ++i)
acc = add_or({add_xor({a.bits[i], b.bits[i]}), acc});
return acc; }
void construct_network(int n, int m, int k) {
ZERO = add_and(make_op(0, add_not(0)));
ONE = add_not(ZERO);
for (int i = 0; i < n; ++i) { // get rows
vector<int> inp(m);
iota(begin(inp), end(inp), i * m);
rows[i] = add_xor(inp); }
for (int j = 0; j < m; ++j) { // get cols
vector<int> inp(n);
for (int index = 0; index < n; ++index)
inp[index] = index * m + j;
cols[j] = add_xor(inp); }
State row_dif = make_state();
State col_dif = make_state();
for (int i = 0; i < m; ++i)
col_dif = inc_if(col_dif, add_xor({col_dif.inc, cols[i]}));
for (int i = 0; i < n; ++i)
row_dif = inc_if(row_dif, add_xor({row_dif.inc, rows[i]}));
State ans = add(row_dif, col_dif);
add_not(different(ans, make_state(k))); }
