An $N$ by $M$ grid of characters is called good if it satisfies these three conditions:

• Each character is either A, B, or C.
• Every $2$ by $2$ subgrid contains all three different letters.
• Any two cells that share exactly one corner contain different letters.

Let $(x,y)$ denote the cell in the $x$-th row from the top and $y$-th column from the left.

You want to construct a good grid that satisfies some of $K$ constraints. Each constraint consists of a positive integer value $a_i$ and two cells $(x_{i1},y_{i1})$ and $(x_{i2},y_{i2})$ that share an edge. You will get $a_i$ points if your good grid has the same letter in cells $(x_{i1},y_{i1})$ and $(x_{i2},y_{i2})$.

Find a good grid that gets the most total number of points.

Constraints

$2\le N,M\le 50$

$0\le K\le 5000$

For all $i$:

• $1\le a_i\le {10}^9$
• $1\le x_{i1},x_{i2}\le N$
• $1\le y_{i1},y_{i2}\le M$
• $|x_{i1}-x_{i2}|+|y_{i1}-y_{i2}|=1$

Input Specification

The first line contains three space-separated integers: $N$, $M$, and $K$.

The next $K$ lines contain five space-separated integers: $a_i$, $x_{i1}$, $y_{i1}$, $x_{i2}$, and $y_{i2}$.

Output Specification

On the first line, output the maximum total number of points obtainable by a good grid.

On the next $N$ lines, output a good grid that obtains this total number of points. If there are many possible good grids, output any of them.

Scoring

For each test case:

• You will receive $100\mathrm{\%}$ of the points if your first line of output contains the correct answer and the remaining lines contain a correctly formatted good grid that obtains this total number of points.
• Otherwise, you will receive $80\mathrm{\%}$ of the points if your first line of output contains the correct answer. You do not need to print anything after the first line if you are aiming for these partial points, as long as you ensure that the first line is terminated by a \n character. You will still receive these partial points if you output a malformatted or incorrect grid.
• Otherwise, you will receive $0$ points.

Your final score is the minimum score over all test cases.

Sample Input

3 4 6
3 1 2 1 3
1 2 3 1 3
4 3 4 2 4
1 2 2 3 2
5 2 1 2 2
9 2 1 2 2

Sample Output

21
BAAA
CCBC
BAAC

Explanation

This grid is good and satisfies the $1$st, $3$rd, $5$th, and $6$th constraints, for a total of $3+4+5+9=21$ points. It can be proven that it is impossible to obtain more than $21$ points.