You have an $n \times m$ grid. Let $(x, y)$ denote the cell in the $x$-th row and $y$-th column of the grid, where the top-left cell is $(1, 1)$ and the bottom-right cell is $(n, m)$.

A cell $(wx, wy)$ has been removed from the grid. You need to determine whether there exists a Hamiltonian path starting from $(sx, sy)$. If one exists, output any valid solution (a Hamiltonian path starting at $(sx, sy)$ that does not pass through $(wx, wy)$).

Input

There are multiple test cases. The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains six positive integers $n, m, wx, wy, sx, sy$, as described in the problem statement. It is guaranteed that $1 \le wx, sx \le n$, $1 \le wy, sy \le m$, and $(wx, wy) \neq (sx, sy)$.

Output

For each test case:

If no solution exists, output a single integer $-1$. Otherwise:

First, output a single positive integer $len$, representing the length of the Hamiltonian path. Clearly, $len = nm - 1$.

Then, output $len$ lines, each containing two positive integers $(x, y)$, representing the coordinates of the cells visited at each step. The first line must be $(sx, sy)$.

Examples

Input 1

3
2 5 2 3 1 1
4 4 2 2 1 1
5 5 1 1 5 1

Output 1

9
1 1
2 1
2 2
1 2
1 3
1 4
2 4
2 5
1 5
-1
24
5 1
4 1
3 1
2 1
2 2
1 2
1 3
1 4
1 5
2 5
3 5
4 5
5 5
5 4
5 3
5 2
4 2
3 2
3 3
2 3
2 4
3 4
4 4
4 3

Note 1

The solution for the first test case is as follows:

For the second test case, it can be proven that no valid solution exists.

The solution for the third test case is as follows:

Subtasks

For all data, it is guaranteed that $1 \le n, m \le 200$ and $\sum (n + m) \le 2000$.