#include "vision.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> get_short(vector<int> ns) {
    map<int, int> cnt;
    for (auto vl : ns) {
        cnt[vl]++;
    }
    vector<int> ns2;
    for (auto [vl, c] : cnt) {
        if (c % 2 == 1) {
            ns2.push_back(vl);
        }
    }
    if (ns2.empty()) {
        ns2.push_back(0);
        ns2.push_back(0);
    }
    return ns2;
}

vector<vector<int>> multiply(vector<int> a, vector<int> b, bool fl = false) {
    vector<vector<int>> res(a.size() + b.size() - 1);
    if (a.size() == 1) {
        for (int i = 0; i < (int)res.size(); ++i) {
            res[i].push_back(add_and({a[0], b[i]}));
        }
        return res;
    }
    if (a.size() <= 5) {
        for (int i = 0; i < (int)a.size(); ++i) {
            for (int j = 0; j < (int)b.size(); ++j) {
                res[i + j].push_back(add_and({a[i], b[j]}));
            }
        }
        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_xor({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_xor({b1[i], b2[i]});
        } else if (i < (int)b1.size()) {
            b12[i] = b1[i];
        } else {
            b12[i] = b2[i];
        }
    }

    vector<vector<int>> res1 = multiply(a1, b1), res2 = multiply(a12, b12), res3(a2.size() + b2.size() - 1);
    if (!fl) {
        res3 = multiply(a2, b2);
    }
    vector<vector<int>> temp(res.size());
    for (int i = 0; i < (int)res2.size(); ++i) {
        if (i < (int)res1.size() && i < (int)res2.size()) {
            for (auto vl : res1[i]) {
                temp[i + a1.size()].push_back(vl);
            }
            for (auto vl : res3[i]) {
                temp[i + a1.size()].push_back(vl);
            }
        } else if (i < (int)res1.size()) {
            for (auto vl : res1[i]) {
                temp[i + a1.size()].push_back(vl);
            }
        } else if (i < (int)res3.size()) {
            for (auto vl : res3[i]) {
                temp[i + a1.size()].push_back(vl);
            }
        }
    }
    for (int i = 0; i < (int)res1.size(); ++i) {
        for (auto vl : res1[i]) {
            temp[i].push_back(vl);
        }
    }
    for (int i = 0; i < (int)res2.size(); ++i) {
        for (auto vl : res2[i]) {
            temp[i + a1.size()].push_back(vl);
        }
    }
    for (int i = 0; i < (int)res3.size(); ++i) {
        for (auto vl : res3[i]) {
            temp[i + a1.size() + b1.size()].push_back(vl);
        }
    }

    return temp;
}

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<vector<int>> res = multiply(a, b);
    hd[0] = add_xor(hs);
    for (int i = 1; i < h; ++i) {
        // res[h - 1 - i] = get_short(res[h - 1 - i]);
        // int t1 = add_xor(res[h - 1 - i]);
        // hd[i] = t1;
        hd[i] = hs[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) {
        // res[w - 1 - i] = get_short(res[w - 1 - i]);
        // int t1 = add_xor(res[w - 1 - i]);
        // wd[i] = t1;
        wd[i] = ws[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);
}