题目描述

Cuber QQ 喜欢上了对 NPC 问题的研究。他对这些前沿问题非常感兴趣，尤其是著名的典型 NPC 问题——哈密顿路径问题。

在图论中，哈密顿路径是无向图或有向图中一条恰好访问每个顶点一次的路径。数学家们花费了数百年试图寻找解决该问题的通用而优雅的方法，但目前仍然只能在有限的情形下解决它。

Cuber QQ 想更进一步，尝试解决网格图上的哈密顿路径问题。

一个网格图共有 $n\times m$ 个顶点。每个顶点使用坐标 $(x,y)$ 表示，其中

$$1\le x\le n,\qquad 1\le y\le m.$$

顶点 $(x,y)$ 与网格中存在的上下左右相邻顶点相连，即：

$$(x-1,y),\quad (x+1,y),\quad (x,y-1),\quad (x,y+1).$$

普通的网格图哈密顿路径对 Cuber QQ 来说似乎过于简单，因此他决定再进一步：

• 路径不能访问顶点 $(N_x,N_y)$；
• 路径必须从顶点 $(S_x,S_y)$ 出发；
• 除了被禁止访问的顶点 $(N_x,N_y)$ 外，其余所有 $nm-1$ 个顶点都必须恰好访问一次；
• 路径中相邻的两个顶点必须在网格图中相邻。

现在这个问题对 Cuber QQ 来说有些困难，请你帮助他构造这样一条路径。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含六个以空格分隔的整数：

$$n,m,N_x,N_y,S_x,S_y.$$

它们分别表示网格的行数、列数、禁止访问的顶点坐标以及路径起点坐标。

输出格式

对于每组测试数据：

• 如果不存在满足条件的路径，输出一行一个整数 -1；
• 否则，第一行输出一个整数 $nm-1$，表示路径中包含的顶点数量；
• 接下来输出 $nm-1$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示路径中第 $i$ 个访问的顶点。

输出的第一个顶点必须为 $(S_x,S_y)$，且路径不能包含 $(N_x,N_y)$。

如果存在多种合法方案，输出任意一种即可。

样例输入

2
2 4 1 2 1 1
2 4 2 2 1 1

样例输出

7
1 1
2 1
2 2
2 3
2 4
1 4
1 3
-1

数据范围

对于所有测试数据：

$$T\le 2500,$$ $$1\le N_x,S_x\le n\le 200,$$ $$1\le N_y,S_y\le m\le 200,$$

并且禁止访问的顶点与起点不同，即：

$$N_x\ne S_x\quad\text{或}\quad N_y\ne S_y.$$

此外，保证所有测试数据满足：

$$\sum (n+m)\le 10^5.$$