#include "vision.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> multiply(vector<int> a, vector<int> b) {
    vector<int> res(a.size() + b.size() - 1);
    for (int i = 0; i < (int)res.size(); ++i) {
        vector<int> temp;
        for (int j = 0; j < (int)a.size(); ++j) {
            if (i - j >= 0 && i - j < (int)b.size()) {
                temp.push_back(add_and({a[j], b[i - j]}));
            }
        }
        res[i] = add_or(temp);
    }
    return res;
}

void construct_network(int h, int w, int k) {
    vector<int> hs(h), ws(w);
    for (int i = 0; i < h; ++i) {
        vector<int> ns;
        for (int j = 0; j < w; ++j) {
            ns.push_back(i * w + j);
        }
        hs[i] = add_or(ns);
    }
    for (int i = 0; i < w; ++i) {
        vector<int> ns;
        for (int j = 0; j < h; ++j) {
            ns.push_back(j * w + i);
        }
        ws[i] = add_or(ns);
    }
    vector<int> hd(h), wd(w);
    vector<int> a = hs, b = hs;
    reverse(b.begin(), b.end());
    vector<int> res = multiply(a, b);
    hd[0] = add_xor(hs);
    for (int i = 1; i < h; ++i) {
        hd[i] = add_or({res[h - 1 - i], res[h - 1 + i]});
    }
    a = ws, b = ws;
    reverse(b.begin(), b.end());
    res = multiply(a, b);
    wd[0] = add_xor(ws);
    for (int i = 1; i < w; ++i) {
        wd[i] = add_or({res[w - 1 - i], res[w - 1 + i]});
    }
    vector<int> temp;
    for (int i = 0; i < (int)hd.size() && i <= k; ++i) {
        if (k - i < (int)wd.size()) {
            if (w != 1 && h != 1) {
                temp.push_back(add_and({hd[i], wd[k - i]}));
            } else if (i == 0 || i == k) {
                temp.push_back(add_and({hd[i], wd[k - i]}));
            }
        }
    }
    add_or(temp);
}