Roundgod draws a grid graph of size with cells. She can use one of colors to color every edge once, but lzr gives her some limits.

1. lzr loves balance. All colors should appear in the same number of times.
2. lzr loves complexity. The graph should not contain any monochromatic cycle.
3. lzr hates monotone. Each whole horizontal or vertical line of the graph should contain at least two colors.

Roundgod is so divine that she doesn't want to waste her god's power to solve this problem. Could you give her a solution?

输入描述:

The input contains multiple test cases. The first line of input contains one integer .
In the following  lines, each line contains two integers  describing one test case.

输出描述:

For each test case, if there's no solution, please output "-1".
Otherwise, output  lines. 
For the first  lines, each line contains  integers, denoting colors of edges on every horizontal line.
For the last  lines, each line contain  integers, denoting colors of edges on every vertical line.

2
2 3
2 5

1 2
3 1
3 2
1 3
2 1
2 3
-1