D. Differences
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a board of dimensions $$$n \times m$$$ initially empty and $$$n \cdot m$$$ chips, where the $$$i$$$-th one has an integer number $$$a_i$$$ written on it. Find a way to place the $$$n \cdot m$$$ chips on the board so that the difference between the numbers of any pair of chips placed in adjacent squares is odd. (Two squares are adjacent if they share a side).

Input

The first line contains an integer $$$T$$$, the number of cases to process.

The first line of each case contains $$$n$$$, $$$m$$$, the dimensions of the board.

The second line contains $$$n \cdot m$$$ integers $$$a_1, a_2, \ldots, a_{n \cdot m}$$$.

Output

For each case, you should print $$$n$$$ lines, each of them with $$$m$$$ integers representing a valid placement of the chips on the board. If there is no valid solution, print a single line with a $$$-1$$$.

Scoring
  1. (32 points) $$$n = 1$$$.
  2. (33 points) $$$n \cdot m$$$ is even.
  3. (35 points) No additional restrictions.
Example
Input
2
2 3
1 2 2 3 4 1
1 2
1 1
Output
1 2 3
2 1 4
-1
Note

$$$1 \le T \le 10^5$$$.

$$$1 \le n \cdot m \le 10^5$$$.

The sum of $$$n \cdot m$$$ over all cases will be at most $$$10^5$$$.

$$$1 \le a_i \le 10^9$$$.