Instead of overwriting with \(X_i\), let us overwrite with \(i\). If this problem is solved, the original problem can be solved by replacing \(i\) with \(X_i\) at last.

After the operations end, the integer written on \((r, c)\) must be the largest \(i\) such that \(r \le R_i, c \le C_i\). To find this, it is sufficient to solve the following problem:

• Write integers to some of the cells in a grid. Then, for each cell, find the maximum value written in the bottom-right rectangular-region relative to itself.

This can be solved by applying the same trick as the two-dimensional cumulative sum trick, from bottom-right to top-left. The time complexity is \(O(HW + Q)\).

Sample Code (PyPy)

h, w, q = map(int, input().split())

a = [[0] * w for i in range(h)]
xs = ["A"]
for i in range(1, q + 1):
    r, c, x = input().split()
    xs.append(x)
    a[int(r)-1][int(c)-1] = i

for r in range(h - 1, -1, -1):
    for c in range(w - 1, -1, -1):
        if r != 0: a[r-1][c] = max(a[r][c], a[r-1][c])
        if c != 0: a[r][c-1] = max(a[r][c], a[r][c-1])

for r in range(h):
    print("".join(xs[a[r][c]] for c in range(w)))