P10828 [EC Final 2020] Fillomino

Prof. Pang is the king of Pangland. Pangland is a board with size $n\times m$. The cell at the $i$-th row and the $j$-th column is denoted as cell $(i, j)$ for all $1\le i\le n, 1\le j\le m$. If two cells share an edge, they are connected. The board is $\textbf{toroidal}$, that is, cell $(1,y)$ is also connected to $(n,y)$ and $(x,1)$ is also connected to $(x,m)$ for all $1\le x\le n, 1\le y\le m$. Prof. Pang has three sons. We call them the first son, the second son and the third son. Each of them lives in a cell in Pangland. The $i$-th son lives in cell $(x_i, y_i)$. No two sons live in the same cell. Prof. Pang wants to distribute the cells in Pangland to his sons such that - Each cell belongs to exactly one son. - There are $cnt_i$ cells that belong to the $i$-th son for all $1\le i\le 3$. - The cells that belong to the $i$-th son are connected for all $1\le i\le 3$. - The cell that the $i$-th son lives in must belong to the $i$-th son himself for all $1\le i\le 3$. Please help Prof. Pang to find a solution if possible.

The first line contains a single integer $T$ ($1\leq T\leq 10^5$) denoting the number of test cases. For each test case, the first line contains two integers $n, m$ ($3\leq n,m \leq 500$) separated by a single space. The next line contains three positive integers $cnt_1,cnt_2,cnt_3$ ($cnt_1+cnt_2+cnt_3 = n m$) separated by single spaces. The $i$-th line of the next $3$ lines contains two integers $x_i, y_i$ ($1\le x_i\le n, 1\le y_i\le m$) separated by a single space. It is guaranteed that $(x_1,y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ are distinct. It is guaranteed that the sum of $nm$ over all test cases is no more than $10^6$.

For each test case, if there is no solution, output $\texttt{-1}$ in one line. Otherwise, output $n$ lines. Each line should contain $m$ characters. The $j$-th character in the $i$-th line should be $\texttt{A}$ if cell $(i, j)$ belongs to the first son, $\texttt{B}$ if cell $(i, j)$ belongs to the second son and $\texttt{C}$ if cell $(i, j)$ belongs to the third son. Cell $(x_i, y_i)$ must belong to the $i$-th son for all $1\le i\le 3$. The cells that belong to the $i$-th son must be connected for all $1\le i\le 3$.