{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cb\u003eIt is preferrable to read the pdf statment.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eCuber QQ fell in love with research of NPC problem. He is very passionate in those cutting-edge thinkings, especially in Hamiltonian path problem, which is a well-known typical NPC problem.\u003cbr\u003e\u003cbr\u003eIn the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. Mathematicians have spent hundreds of years, trying to find a general yet elegant solution of this problem, but still, the problem is only solved in a limited scope.\u003cbr\u003e\u003cbr\u003eCuber QQ wants to take one step forward, by solving the Hamiltonian path problem in the grid. A grid has $n \\times m$ vertices. We use a typical coordinate system in the grid, where each vertex on the grid is labelled by a pair of integers $(x, y)$ $(1 \\le x \\le n, 1 \\le y \\le m)$, and it is connected to adjacent vertices (if they are available), i.e., $(x-1, y)$, $(x+1, y)$, $(x, y-1)$, $(x, y+1)$.\u003cbr\u003e\u003cbr\u003eThe problem seems too trivial to him, Cuber QQ will take another step forward to find a Hamiltonian path in the grid without visiting the vertex $(N_x,N_y)$ $(1 \\le N_x \\le n, 1 \\le N_y \\le m)$, and the starting vertex must be located at $(S_x,S_y)$ $(1 \\le S_x \\le n, 1 \\le S_y \\le m)$. It is a little too difficult for him now and he asks you for help.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$ ($T \\le 2~500$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case has six space-separated integers $n,m,N_x,N_y,S_x,S_y$ ($1\\le N_x,S_x\\le n \\le 200$, $1\\le N_y, S_y\\le m \\le 200$, $N_x\\neq S_x$ or $N_y \\neq S_y$) in one line.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that $\\sum n+m\\le 10^5$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, if there is no solution, print a single integer $-1$ in one line, otherwise the first line output an integer $nm - 1$, which is the length of the path. The next $nm - 1$ lines contain the vertices in the visiting order. and each of the $n$ lines contains two space-separated integers $x,y$ ($1 \\le x \\le n, 1 \\le y \\le m$).\u003cbr\u003e\u003cbr\u003eIf there are multiple solutions, print any.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 4 1 2 1 1\r\n2 4 2 2 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n1 1\r\n2 1\r\n2 2\r\n2 3\r\n2 4\r\n1 4\r\n1 3\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}