M. Fillomino
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 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.

Input

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$$$.

Output

For each test case, if there is no solution, output "-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 'A' if cell $$$(i, j)$$$ belongs to the first son, 'B' if cell $$$(i, j)$$$ belongs to the second son and '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$$$.

Example
Input
2
3 3
1 3 5
1 1
2 2
3 3
4 4
5 5 6
2 2
2 3
3 3
Output
ABB
CBC
CCC
BABB
BABC
CACC
AACC