#include "vision.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
vi rows, cols;
void construct_network(int H, int W, int K) {
rows = vi(H);
loop(i, H) {
vi Ns;
loop(j, W) {
Ns.push_back(i * W + j);
}
rows[i] = add_or(Ns);
//add_log(rows[i]);
}
cols = vi(W);
loop(j, W) {
vi Ns;
loop(i, H) {
Ns.push_back(i * W + j);
}
cols[j] = add_or(Ns);
//add_log(cols[j]);
}
vi rowBits;
loop(bit, 8) {
vi ands;
loop(i, H - (1 << bit)) {
vi rs;
for (int j = i + (1 << bit); j < H; j += 2 * (1 << bit)) {
for (int j2 = j; j2 < min(H, j + (1 << bit)); j2++) {
rs.push_back(rows[j2]);
}
}
if (rs.size() == 0) {
break;
}
int l = rows[i];
int r = add_or(rs);
ands.push_back(add_and({l, r}));
}
if (ands.size() == 0) {
break;
}
rowBits.push_back(add_or(ands));
//add_log(rowBits.back());
}
vi colBits;
loop(bit, 8) {
vi ands;
loop(i, W - (1 << bit)) {
vi rs;
for (int j = i + (1 << bit); j < W; j += 2 * (1 << bit)) {
for (int j2 = j; j2 < min(W, j + (1 << bit)); j2++) {
rs.push_back(cols[j2]);
}
}
if (rs.size() == 0) {
break;
}
int l = cols[i];
int r = add_or(rs);
ands.push_back(add_and({l, r}));
}
if (ands.size() == 0) {
break;
}
colBits.push_back(add_or(ands));
//add_log(colBits.back());
}
const int zero = add_not(add_or(rows));
if (colBits.size() > rowBits.size()) {
swap(colBits, rowBits);
}
vi sum;
int carry = zero;
loop(bit, colBits.size()) {
sum.push_back(add_xor({colBits[bit], rowBits[bit], carry}));
carry = add_or({
add_and({colBits[bit], rowBits[bit]}),
add_and({colBits[bit], carry}),
add_and({carry, rowBits[bit]})
});
}
for (int bit = colBits.size(); bit < rowBits.size(); bit++) {
sum.push_back(add_xor({rowBits[bit], carry}));
carry = add_and({rowBits[bit], carry});
}
sum.push_back(carry);
loop(bit, sum.size()) {
if ((K & (1 << bit)) == 0) {
sum[bit] = add_not(sum[bit]);
}
}
if (K >= (1 << sum.size())) {
add_not(add_not(zero));
return;
}
add_and(sum);
}
