#include "vision.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
int gid(int x, int y){
return x * m + y;
}
namespace sub125{
void solve(){
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int x = i; x < n && x - i <= k; x++){
int d = k - x + i, y = j - d;
if(y > -1){
cnt++;
add_and({gid(i, j), gid(x, y)});
}
if((y = j + d) < m){
cnt++;
add_and({gid(i, j), gid(x, y)});
}
}
}
}
vector<int>p(cnt);
iota(p.begin(), p.end(), n * m);
add_or(p);
}
}
namespace sub3{
void solve(){
vector<int>p;
for(int i = 0, cnt = n * m - 1; i < n; i++){
for(int j = 0; j < m; j++){
vector<int>s;
for(int x = i; x < n && x - i <= k; x++){
int d = k - x + i, y = j - d;
if(y > -1){
s.push_back(gid(x, y));
}
if((y = j + d) < m){
s.push_back(gid(x, y));
}
}
if(!s.empty()){
add_or(s);
add_and({gid(i, j), cnt + 1});
p.push_back(cnt += 2);
}
}
}
add_or(p);
}
}
namespace sub7{
void solve(){
int id = n * m - 1;
vector<int>row(n), col(m);
for(int i = 0; i < n; row[i++] = ++id){
vector<int>p(m);
for(int j = 0; j < m; j++){
p[j] = gid(i, j);
}
add_or(p);
}
for(int i = 0; i < m; col[i++] = ++id){
vector<int>p(n);
for(int j = 0; j < n; j++){
p[j] = gid(j, i);
}
add_or(p);
}
add_or(row);
add_xor(row);
add_and({id + 1, id + 2});
int one_row = (id += 3);
vector<int>p;
for(int i = 1; i < m; i++, p.push_back(++id)){
add_and({col[i - 1], col[i]});
}
add_or(p);
add_and({++id, one_row});
one_row = ++id;
add_or(col);
add_xor(col);
add_and({id + 1, id + 2});
p.clear();
int one_col = (id += 3);
for(int i = 1; i < n; i++, p.push_back(++id)){
add_and({row[i - 1], row[i]});
}
add_or(p);
add_and({++id, one_col});
add_or({++id, one_row});
}
}
namespace sub468{
int id;
void work(vector<int>& val){
for(int bit = 7, N = val.size(); bit > -1; bit--){
if((1 << bit) <= N){
int have_1 = ++id;
vector<int>p(val.begin(), val.begin() + (1 << bit));
add_or(p);
add_not(id++);
for(int i = 0; i + (1 << bit) < N; val[i++] = (id += 3)){
add_and({val[i], have_1});
add_and({val[i + (1 << bit)], have_1 + 1});
add_or({id + 1, id + 2});
}
for(int i = N - (1 << bit); i < N; val[i++] = ++id){
add_and({val[i], have_1});
}
}
}
}
void solve(){
id = n * m - 1;
vector<int>row(n - 1), col(m - 1);
for(int i = 0; i + 1 < n; row[i++] = ++id){
vector<int>p(m);
for(int j = 0; j < m; j++){
p[j] = gid(i, j);
}
if(i > 0){
p.push_back(row[i - 1]);
}
add_xor(p);
}
for(int i = 0; i + 1 < m; col[i++] = ++id){
vector<int>p(n);
for(int j = 0; j < n; j++){
p[j] = gid(j, i);
}
if(i > 0){
p.push_back(col[i - 1]);
}
add_xor(p);
}
work(row);
work(col);
if(k == --n + --m){
for(int& i : col){
row.push_back(i);
}
add_and(row);
return;
}
vector<int>p;
if(k <= n){
if(k == n){
if(m > 0){
add_not(col[0]);
add_and({row[n - 1], id + 1});
p.push_back(id += 2);
}
else{
p.push_back(row[n - 1]);
}
}
else if(m > 0){
add_not(col[0]);
add_xor({row[k - 1], row[k]});
add_and({id + 1, id + 2});
p.push_back(id += 3);
}
else{
add_xor({row[k - 1], row[k]});
p.push_back(++id);
}
}
else if(n > 0){
int _k = k - n;
add_xor({col[_k - 1], col[_k]});
add_and({id + 1, row[n - 1]});
p.push_back(id += 2);
}
if(k <= m){
if(k == m){
if(n > 0){
add_not(row[0]);
add_and({col[m - 1], id + 1});
p.push_back(id += 2);
}
else{
p.push_back(col[m - 1]);
}
}
else if(n > 0){
add_not(row[0]);
add_xor({col[k - 1], col[k]});
add_and({id + 1, id + 2});
p.push_back(id += 3);
}
else{
add_xor({col[k - 1], col[k]});
p.push_back(++id);
}
}
else if(m > 0){
int _k = k - m;
add_xor({row[_k - 1], row[_k]});
add_and({id + 1, col[m - 1]});
p.push_back(id += 2);
}
for(int i = 1; i < n; i++){
int j = k - i;
if(j > 0 && j < m){
add_xor({row[i - 1], row[i]});
add_xor({col[j - 1], col[j]});
add_and({id + 1, id + 2});
p.push_back(id += 3);
}
}
add_or(p);
}
}
void construct_network(int _n, int _m, int _k){
k = _k;
if(max(n = _n, m = _m) <= 10 || min(n, m) == 1){
return sub125::solve();
}
if(max(n, m) <= 30){
return sub3::solve();
}
if(k == 1){
return sub7::solve();
}
return sub468::solve();
}
