#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);
    if (a.size() == 1) {
        for (int i = 0; i < (int)res.size(); ++i) {
            res[i] = add_and({a[0], b[i]});
        }
        return res;
    }
    vector<int> a1, a2, b1, b2;
    for (int i = 0; i < (int)a.size() / 2; ++i) {
        a1.push_back(a[i]);
    }
    for (int i = (int)a.size() / 2; i < (int)a.size(); ++i) {
        a2.push_back(a[i]);
    }
    for (int i = 0; i < (int)b.size() / 2; ++i) {
        b1.push_back(b[i]);
    }
    for (int i = (int)b.size() / 2; i < (int)b.size(); ++i) {
        b2.push_back(b[i]);
    }

    vector<int> a12(max(a1.size(), a2.size())), b12(max(b1.size(), b2.size()));
    for (int i = 0; i < (int)a12.size(); ++i) {
        if (i < (int)a1.size() && i < (int)a2.size()) {
            a12[i] = add_or({a1[i], a2[i]});
        } else if (i < (int)a1.size()) {
            a12[i] = a1[i];
        } else {
            a12[i] = a2[i];
        }
    }
    for (int i = 0; i < (int)b12.size(); ++i) {
        if (i < (int)b1.size() && i < (int)b2.size()) {
            b12[i] = add_or({b1[i], b2[i]});
        } else if (i < (int)b1.size()) {
            b12[i] = b1[i];
        } else {
            b12[i] = b2[i];
        }
    }

    vector<int> res1 = multiply(a1, b1), res2 = multiply(a12, b12), res3 = multiply(a2, b2);
    for (int i = 0; i < (int)res2.size(); ++i) {
        if (i < (int)res1.size() && i < (int)res3.size()) {
            int tmp = add_or({res1[i], res3[i]});
            res2[i] = add_xor({res2[i], tmp});
        } else if (i < (int)res1.size()) {
            res2[i] = add_xor({res2[i], res1[i]});
        } else {
            res2[i] = add_xor({res2[i], res3[i]});
        }
    }
    vector<vector<int>> temp(res.size());
    for (int i = 0; i < (int)res1.size(); ++i) {
        temp[i].push_back(res1[i]);
    }
    for (int i = 0; i < (int)res2.size(); ++i) {
        temp[i + a1.size()].push_back(res2[i]);
    }
    for (int i = 0; i < (int)res3.size(); ++i) {
        temp[i + a1.size() + b1.size()].push_back(res3[i]);
    }

    for (int i = 0; i < (int)res.size(); ++i) {
        if (temp[i].size() == 1) {
            res[i] = temp[i][0];
        } else {
            res[i] = add_or(temp[i]);
        }
    }
    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);
}