Tree Propagation on a Lake-Adjacent Grid

We are given an $n\times m$ grid where each cell is referenced by a pair $(x,y)$ (with $1 \le x \le n$, $1 \le y \le m$). There are $q$ non‐overlapping rectangular lakes. The $i$th lake covers the rectangle with its upper‐left corner at $(a_{i,1}, b_{i,1})$ and its lower–right corner at $(a_{i,2}, b_{i,2})$. A cell inside any lake is water; all other cells are land. \par Little Y will perform $r$ tree planting events. The $i$th event occurs at second $t_i$, at which a tree is planted at cell $(x_i, y_i)$. It is guaranteed that the cell is land and that at the moment of planting the cell has no living tree (any previously planted or grown tree there has already died). The planting events are given in non–decreasing order of time. \par Every second the following two processes occur simultaneously: \par

1. (Propagation) For each land cell ( (x,y) ) that does not currently have a living tree, if it is adjacent (in the four–directional sense, i.e. cells ((x+1,y)), ((x-1,y)), ((x,y+1)), ((x,y-1))) to at least one lake and if in the previous second at least one of its adjacent cells had a living tree, then a new tree grows at ( (x,y) ) with age $0$. \par
2. (Death) For each living tree, if it has been alive for more than $k$ seconds (i.e. its age $> k$, counting from the moment it was planted or grew) and all of its adjacent land cells (ignoring water cells) have no living tree, then the tree dies. \par Little Y wonders: after enough time has passed (that is, after the grid reaches a steady state in which no new trees grow and no living trees die), how many living trees will there be in total? \par All formulas are in (\LaTeX) format.

inputFormat

The first line contains two integers (n) and (m) representing the number of rows and columns of the grid.\n\par The second line contains three integers: (q) (the number of lakes), (r) (the number of tree planting events), and (k) (the threshold age for possible death).\n\par Then follow (q) lines, each containing four integers: (a_{i,1}), (b_{i,1}), (a_{i,2}), and (b_{i,2}), which denote that the (i)th lake covers all cells from ((a_{i,1}, b_{i,1})) to ((a_{i,2}, b_{i,2})) (inclusive).\n\par Then follow (r) lines, each containing three integers: (t_i), (x_i), and (y_i), representing a tree planting event at time (t_i) at cell ((x_i,y_i)). The event times (t_i) are given in non–decreasing order.

outputFormat

Output a single integer: the total number of living trees in the grid after the process reaches a steady state.

sample

3 3
0 1 100
1 2 2

0