/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {}

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/
class Solution {
public:
    Node* buildLeaf(bool b) {
        return new Node(b, true, nullptr, nullptr, nullptr, nullptr);
    }
    Node* buildNode() {
        return new Node(false, false, nullptr, nullptr, nullptr, nullptr);
    }
    Node* run(const vector<vector<int>>& g, int si, int sj, int n) {
        if (n==1) return buildLeaf(g[si][sj]);
        else {
            Node* ret = buildNode();
            Node* Node::* chi[4] = {
                &Node::topLeft,
                &Node::topRight,
                &Node::bottomLeft,
                &Node::bottomRight
            };
            const int ii[] = {0, 0, 1, 1};
            const int jj[] = {0, 1, 0, 1};
            for (int k=0; k<4; k++) {
                const int nn = n/2;
                ret->*chi[k] = run(g, si+ii[k]*nn, sj+jj[k]*nn, nn);
            }
            if (all_of(chi, chi+4, [ret](auto x){return (ret->*x)->isLeaf;})) {
                if (count_if(chi, chi+4, [ret](auto x){return (ret->*x)->val;})%4!=0)
                    return ret;
                ret->isLeaf = true;
                ret->val = (ret->*chi[0])->val;
                for (auto x : chi) {
                    delete (ret->*x);
                    ret->*x = nullptr;
                }
            }
            return ret;
        }
    }
    Node* construct(vector<vector<int>>& grid) {
        const int n = grid.size();
        return run(grid, 0, 0, n);
    }
};