#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree {
    vector<int> t;
    int sz = 1;

    void init(const vector<int> &a) {
        sz = size(a);
        t.resize(sz * 4);
        build(1, 0, sz, a);
    }

    void build(int x, int lx, int rx, const vector<int> &a) {
        if (lx + 1 == rx) {
            t[x] = a[lx];
        } else {
            build(x << 1, lx, lx + rx >> 1, a);
            build(x << 1 | 1, lx + rx >> 1, rx, a);
            t[x] = add_or({t[x << 1], t[x << 1 | 1]});
        }
    }

    void rangeSum(int l, int r, vector<int> &a, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            return a.push_back(t[x]);
        }
        int mid = lx + rx >> 1;
        rangeSum(l, r, a, x << 1, lx, mid);
        rangeSum(l, r, a, x << 1 | 1, mid, rx);
    }

    void rangeOr(int l, int r, vector<int> &a) {
        rangeSum(l, r, a, 1, 0, sz);
    }
};

void construct_network(int H, int W, int K) {
    vector pos1(H, vector<int>(W)), pos2(pos1);
    map<int, vector<int>> mp1, mp2;
    map<int, SegmentTree> st1, st2;

    auto toi = [&](int x, int y) {
        return x * W + y;
    };


//    cout << "here!" << endl;

    for (int sum = 0; sum < H + W; ++sum) {
        int top = 0;
        for (int x = 0; x <= sum; ++x) {
            int y = sum - x;
            if (y < W && x < H) {
                mp1[sum].push_back(toi(x, y));
                pos1[x][y] = top++;
            }
        }
    }

//    cout << "here!" << endl;

    for (int sum = -H + 1; sum < W; ++sum) {
        int top = 0;
        for (int x = 0; x < H; ++x) {
            int y = sum + x;
            if (x >= 0 && x < H && y < W) {
                mp2[sum].push_back(toi(x, y));
                pos2[x][y] = top++;
            }
        }
    }

//    cout << "here!" << endl;

    for (auto [x, y] : mp1) {
//        cout << "st1: " << x << endl;
        st1[x].init(y);
    }
    for (auto [x, y] : mp2) {
//        cout << "st2: " << x << endl;
        st2[x].init(y);
    }


//    cout << "here!" << endl;

    vector<int> orz;

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            vector<int> a;
            int lx = -1, rx = -1, sum = -1;
            for (int x1 = 0; x1 <= i; ++x1) {
                int y1 = j - (K - (i - x1));
                if (y1 <= j && y1 >= 0 && y1 < W) {
                    int p = pos1[x1][y1];
                    assert(sum == -1 || sum == x1 + y1);
                    sum = x1 + y1;
                    lx = lx == -1 ? p : lx;
                    rx = p + 1;
                }
            }
            if (sum != -1) {
                st1[sum].rangeOr(lx, rx, a);
            }
            lx = -1, rx = -1, sum = -1;
            for (int x1 = 0; x1 <= i; ++x1) {
                int y1 = j + (K - (i - x1));
                if (y1 >= j && y1 >= 0 && y1 < W) {
                    int p = pos2[x1][y1];
                    assert(sum == -1 || sum == y1 - x1);
                    sum = y1 - x1;
                    lx = lx == -1 ? p : lx;
                    rx = p + 1;
                }
            }
            if (sum != -1) {
                st2[sum].rangeOr(lx, rx, a);
            }
            if (!a.empty()) {
                orz.push_back(add_and({toi(i, j), add_or(a)}));
            }
        }
    }

    add_or(orz);
}