#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
// const int N = 2e5 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;
int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int add_not(int N);
void construct_network(int n, int m, int k) {
if (k == 1 && min(n, m) != 1) {
int cnt = (n * m);
vector<int> v, a1, b1;
vector<int> all;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
v.push_back(i * m + j);
all.push_back(i * m + j);
}
add_xor(v);
a1.push_back(cnt); cnt++;
v = {};
}
add_or(a1);
int cn = cnt; cnt++;
v = {};
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
v.push_back(i * m + j);
}
add_xor(v);
b1.push_back(cnt); cnt++;
v = {};
}
add_or(b1);
int cn1 = cnt; cnt++;
add_xor({cn, cn1}); int vl = cnt; cnt++;
vector<int> nw;
for (int i = 1; i < n; i++) {
add_and({a1[i], a1[i - 1]});
nw.push_back(cnt); cnt++;
}
vector<int> nw1;
for (int i = 1; i < m; i++) {
add_and({b1[i], b1[i - 1]});
nw1.push_back(cnt); cnt++;
}
add_or(nw);
int vl11 = cnt; cnt++;
add_or(nw1);
int vl22 = cnt; cnt++;
int ans = cnt;add_or({vl11, vl22}); cnt++;
add_and({ans, vl});
return;
}
if (max(n, m) <= 30 || min(n, m) == 1) {
vector<int> fnd, tot;
int cnt = (n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int i1 = 0; i1 < n; i1++) {
for (int j1 = 0; j1 < m; j1++) {
int x = abs(i - i1) + abs(j - j1);
if (x == k) {
int v = i * m + j, v1 = i1 * m + j1;
fnd.push_back(v1);
}
}
}
if ((int) fnd.size() > 0) {
int val = cnt; cnt++;
add_or(fnd);
tot.push_back(cnt); cnt++;
add_and({i * m + j, val});
}
fnd = {};
}
}
add_or(tot);
} else {
vector<int> v;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int sm = i + j;
if ((i || j) && sm == k) {
v.push_back(i * m + j);
}
}
if ((int) v.size())
add_or(v);
}
return;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// int n, m, k;
// cin >> n >> m >> k;
// // cout << n << " " << m << " " << k << '\n';
// construct_network(n, m, k);
// }
// return 0;
// }
