div

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        N = (int) matrix.size();
        M = (int) matrix[0].size();
        
        return search(matrix, target, 0, 0, N - 1, M - 1);
    }
    
    bool in(int l, int r, int m) {
        return m >= l && r >= m;
    }
    
    bool valid_position(int i, int j) {
        return i >= 0 && i < N && j >= 0 && j < M;
    }
    
    bool search(vector<vector<int> >& matrix, int target, int ui, int uj, int li, int lj) {
        if (ui == li && uj == lj) {
            return matrix[ui][uj] == target;
        } else {
            int mi = (ui + li) / 2;
            int mj = (uj + lj) / 2;
            
            bool ans = false;
            
            if (!ans && valid_position(ui, uj) && valid_position(mi, mj) && in(matrix[ui][uj], matrix[mi][mj], target)) {
                ans |= search(matrix, target, ui, uj, mi, mj);
            }
            if (!ans && valid_position(ui, mj + 1) && valid_position(mi, lj) && in(matrix[ui][mj + 1], matrix[mi][lj], target)) {
                ans |= search(matrix, target, ui, mj + 1, mi, lj);
            }
            if (!ans && valid_position(mi + 1, uj) && valid_position(li, mj) && in(matrix[mi + 1][uj], matrix[li][mj], target)) {
                ans |= search(matrix, target, mi + 1, uj, li, mj);
            }
            if (!ans && valid_position(mi + 1, mj + 1) && valid_position(li, lj) && in(matrix[mi][mj], matrix[li][lj], target)) {
                ans |= search(matrix, target, mi + 1, mj + 1, li, lj);
            }
            return ans;
        }
    }