题目描述

A long time ago, before our modern civilization arose and before any of you were born, was the year -1966 (3961 Before SWERC). During this dark period, there were no streaming services nor any programming contests. Thus, to entertain themselves, humans had rudimentary games that they played on clay tablets.

This year, a mysterious game was created: Kakurus. We know close to nothing about Kakurus (the Internet Archive had not yet been created), except for a few rules described on an artifact you have discovered:

1. The game is played on a $M \times N$ grid;
2. Each cell is either black or white;
3. White cells are originally empty, but you will have to put an integer from $1$ to $9$ (inclusive) inside each white cell;
4. Horizontal constraint: A black cell can contain an integer corresponding to the sum of the consecutive white cells to its right (until the first black cell or the limit of the grid);
5. Vertical constraint: A black cell can contain an integer corresponding to the sum of the consecutive white cells below it (until the first black cell or the limit of the grid).

Note that the last two rules are independent from each other: a black cell can have $0$, $1$ or $2$ integers inside it. Note also that no constraint is placed on repetitions of numbers. Finally, since we want this problem to be interesting, every white cell is covered by exactly one vertical constraint and by exactly one horizontal constraint.

At the bottom of your artifact lies a grid of Kakurus. It is already filled, but not necessarily with a correct solution – probably a deterioration due to the age of this antique artifact. Can you find a valid solution that is as close as possible to this proposed solution?

If the number you write on a white cell is $X$ and the value of the proposed solution for this cell is $T$, then the closeness score is $|X - T|$. The final closeness score of the grid is the sum of all closeness scores of the cells. Your objective is to find the minimum closeness score that can be achieved.

输入格式

The first line of the input consists of three integers, $M$, $N$ and $S$, respectively the number of lines and columns of this grid, and the number of sum constraints.

Then, $M$ lines follow. The $i$th of these lines only contains digits from $0$ to $9$. The $j$th character equals $0$ if and only if the cell at line $i$ and column $j$ ($1 \leq i \leq M$, $1 \leq j \leq N$) is black, and otherwise is equal to the value of this cell (which is thus white) in the proposed solution.

Then $S$ lines follow. Each line is of the form $c\ i\ j\ s$ where $c$ is equal to either $H$ or $V$, $1 \leq i \leq M$, $1 \leq j \leq N$ and $s$ is an integer between $1$ and $135$, inclusive. The sum of the consecutive white cells at the right of (when $c = H$) or below (when $c = V$) the cell at line $i$ and column $j$ must be equal to $s$ in your solution.

It is guaranteed that every white cell is covered by exactly one vertical and one horizontal constraint.

输出格式

If the grid has no solution, you must output IMPOSSIBLE. Otherwise, your output should consist of the minimum closeness score that can be achieved.

4 4 7
0000
0032
0233
0204
H 3 1 9
V 1 3 6
H 2 2 5
V 2 2 5
V 1 4 9
H 4 1 2
H 4 3 4

1

3 4 5
0000
0012
0345
H 2 2 3
H 3 1 12
V 2 2 3
V 1 3 5
V 1 4 6

IMPOSSIBLE

提示

Limits

• $1 \leq M \leq 16$
• $1 \leq N \leq 16$
• $0 \leq S \leq 2 \times M \times N$