403544: GYM101192 F Stone, grass and fire

Farmer Lyosha owns a rectangular field. The field has n rows and m columns. Field cells positions are denoted by pairs of numbers (i, j), where i is the row index and j is the column index. Each cell of the field has either grass (denoted by character '.’) or stone (denoted by character 'X’).

Disasters happen, and Lyosha's field is on fire. The fire has started in different cells. There are k fire sources. The i-th fire source has started in grass cell (x_i, y_i) and it will burn for c_i seconds. Each second the fire spreads from an already burning cell to adjacent cells that have a common edge with the burning cell. If in current cell fire will burn for c second, then this fire will burn for c - 1 seconds in adjacent cells. The fire did not spread to adjacent cells, if it will burn for zero seconds in current cell.

Assume that all fire sources are independent. All fire sources have distinct coordinates. Stone does not burn.

Lyosha is very eager to know how many grass cells are going to burn down.

The first input line contains three integer numbers — n, m, k — which denote the field size and the number of fire sources. Following that are n lines describing the field, each line has m characters. The j-th character in the i-th line denotes type of the (i, j) cell. The next k lines each contain three integer numbers x_i, y_i, c_i that describe the i-th fire source.

Output one integer number: the number of grass cells that will burn down.

4 5 2
.X...
.X.X.
.X.X.
...X.
1 3 1
3 3 4

9