#361 Uncool Grid

Statement

Statement language

You are given an $N$ by $M$ grid $A$ . Each cell contains either $0$ or $1$ .

A shortest path from $(1,1)$ to $(N,M)$ moves one cell to the right or one cell downward at every step. Reading the characters on the visited cells from the start to the end produces a binary string of length $N+M-1$ .

The grid is called cool if two distinct shortest paths can produce the same binary string. Otherwise, equivalently, if every shortest path produces a different binary string, the grid is not cool.

Choose exactly $K$ distinct cells and flip each chosen cell once. A $0$ becomes $1$ , and a $1$ becomes $0$ .

Construct one grid that is not cool after exactly $K$ flips. If this is impossible, report that it is impossible.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the answer.

If no valid grid can be constructed, print -1 on one line.

Otherwise, print $N$ binary strings of length $M$ . The printed grid must differ from the original grid in exactly $K$ cells and must not be cool.

If there are multiple solutions, print any of them.

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N,M \leq 3\,000$ .
.

Subtasks

#	Score	Constraints
1	8	$\min(N,M)=1$ .
2	14	Every $A_{i,j}$ is .

Samples

Input

Output

In the second test case, flipping cell $(1,2)$ changes exactly one cell. In the third test case there is only one shortest path, so the printed grid also satisfies the requirement.