The final color of each cell is only dependent on the last operation against it. In such situation, considering the operations in reverse order often makes it easy to solve.

By considering the operations in reverse order, the procedure in the problem statement turns out to be equivalent to the following:

You are given a grid with \(H\) rows and \(W\) columns. Initially, the colors of all cells are undetermined.

Perform the following operation for each \(i = M,M-1,\ldots,1\) in order.

• If \(T_i = 1\), determine the color of each cell in row \(A_i\) with undetermined color to be \(X_i\).

• If \(T_i = 2\), determine the color of each cell in column \(A_i\) with undetermined color to be \(X_i\).

After the iteration, determine the color of each cell with undetermined color to be color \(0\).

This way, it turns out that the answer can be obtained by processing the number of operated rows and columns, whether each row and column is operated or not, and the number of determined cells with each color.

Specifically, an operation against the \(A_i\)-th row may be considered effective only when no prior operation is performed against the \(A_i\)-th row, in which case the number of determined cells with color \(X_i\) increases by the number of untouched columns; same applies to one against the \(A_i\)-th column.

Sample code

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
    int h, w, m;
    cin >> h >> w >> m;
    vector<bool> f(h), g(w); // Whether each row/column is touched or not
    ll hc = h, wc = w; // The number of untouched rows/columns
    vector<int> t(m), a(m), x(m);
    rep(i, m) cin >> t[i] >> a[i] >> x[i];
    rep(i, m) a[i]--;
    int X = 200010;
    vector<ll> cnt(X); // The number of determined cells with each color
    for (int i = m - 1; i >= 0; i--) {
        if (t[i] == 1) {
            if (!f[a[i]]) {
                hc--;
                f[a[i]] = true;
                cnt[x[i]] += wc;
            }
        }
        else {
            if (!g[a[i]]) {
                wc--;
                g[a[i]] = true;
                cnt[x[i]] += hc;
            }
        }
    }
    cnt[0] += hc * wc;
    vector<pair<ll, ll>> ans;
    rep(i, X) if (cnt[i]) ans.push_back({ i,cnt[i] });
    cout << ans.size() << '\n';
    for (auto p : ans) cout << p.first << ' ' << p.second << '\n';
}