#include <bits/stdc++.h>
#define forint(i, N) for (int i = 0; i < (N); i++)
using namespace std;
//vector<int> v = {1, 0, 0, 0, 1, 0};
//vector<int> v = {0, 1, 0, 1, 0, 0};
vector<int> v = {0, 0, 1, 1, 0, 0};
int add_not(int N);
int add_and(vector<int> N);
int add_or(vector<int> N);
int add_xor(vector<int> N);
int cc;
/*
int is_k(int& pos, vector<int>& vec, int k) {
vector<int> vec_test;
forint(i, vec.size() - k) {
pos++;
vec_test.push_back(pos);
add_and({vec[i], vec[i + k]});
}
pos++;
add_or(vec_test);
return pos;
}
int is_at_most_k(int& pos, vector<int>& vec, int k) {
// == 0
pos++;
add_xor(vec);
pos++;
add_not(pos-1);
vector<int> vec2 = {pos};
// >= 1
forint(i, vec.size() - k) {
vector<int> tmp;
for (int j = i; j <= i + k; j++) {
tmp.push_back(vec[j]);
}
pos++;
add_xor(tmp);
pos++;
add_or(tmp);
pos++;
add_and({pos-2, pos-1});
vec2.push_back(pos);
}
pos++;
add_or(vec2);
return pos;
}
*/
int is_k(vector<int>& vec, int k) {
//for(auto i:vec) {
// cerr << v[i] << " ";
//}
vector<int> vec_test;
forint(i, vec.size() - k) {
//int j;
vec_test.push_back(add_and({vec[i], vec[i + k]}));
//cerr << v[vec[i]] << "&" << v[vec[i+k]] << "=" << v[j] << "<-\n";
}
return add_or(vec_test);
}
int is_at_most_k(vector<int>& vec, int k) {
//for(auto i:vec) {
// cerr << v[i] << " ";
//}
// == 0
//int j;
vector<int> vec2 = {add_xor(vec)};
//cerr << v[j] << " -XOR- " << endl;
// >= 1
forint(i, vec.size() - k) {
//cerr << i << " ------- " << endl;
vector<int> tmp;
for (int j = i; j <= i + k; j++) {
tmp.push_back(vec[j]);
}
vec2.push_back(add_and({add_not(add_xor(tmp)), add_or(tmp)}));
//cerr << v[j] << " ++ " << endl;
}
return add_or(vec2);
}
void construct_network(int h, int w, int k) {
cc = h * w - 1;
vector<int> right;
int vsize = h * w - 1;
for (int i = h - 1; i >= 1; i--) {
int a = i;
int b = 0;
vector<int> tmp;
while (b < w && a < h) {
//cerr << a * w + b << " ";
tmp.push_back(a * w + b);
a++;
b++;
}
//cerr << endl << " r";
vsize++;
right.push_back(vsize);
add_or(tmp);
}
for (int i = 0; i < w; i++) {
int a = 0;
int b = i;
vector<int> tmp;
while (b < w && a < h) {
//cerr << a * w + b << " ";
tmp.push_back(a * w + b);
a++;
b++;
}
//cerr << endl << " r";
vsize++;
right.push_back(vsize);
add_or(tmp);
}
//cerr << vsize << " right diagonal" << endl;
vector<int> left;
for (int i = 0; i < h - 1; i++) {
int a = i;
int b = 0;
vector<int> tmp;
while (b < w && a >= 0) {
tmp.push_back(a * w + b);
a--;
b++;
}
vsize++;
left.push_back(vsize);
add_or(tmp);
}
for (int i = 0; i < w; i++) {
int a = h - 1;
int b = i;
vector<int> tmp;
while (b < w && a >= 0) {
tmp.push_back(a * w + b);
a--;
b++;
}
vsize++;
left.push_back(vsize);
add_or(tmp);
}
/*
add_and({is_k(vsize, right, k), is_at_most_k(vsize, left, k)});
int a = ++vsize;
add_and({is_k(vsize, left, k), is_at_most_k(vsize, right, k)});
int b = ++vsize;
*/
//int a, b;
add_or({
add_and({is_k(right, k), is_at_most_k(left, k)}),
add_and({is_k(left, k), is_at_most_k(right, k)})
});
//cerr << v[a] << " -- " << v[b] << endl;
}
