{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e通常,智能手机可以通过密码、指纹识别或面部识别来锁定。还有另一种常用的方法:\u003cspan class\u003d\"tex-font-style-it\"\u003e图案锁\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e图案锁\u003c/span\u003e允许您通过在屏幕上绘制图案来锁定和解锁设备。该图案是通过在网格上连接一系列点的多边形路径来绘制的。锁定屏幕上的点阵有$$$n$$$行和$$$m$$$列。行与行之间以及列与列之间的间距相等。我们用$$$x$$$行$$$y$$$列的点表示为$$$(x,y)$$$。我们使用一系列点来表示图案,即多边形路径。例如,序列$$$\\{(1,1),(2,3),(3,2),(2,2)\\}$$$可以表示下面图片中显示的图案。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/6423b3cfc43f37980d94bf3595648f3d?v\u003d1713865910\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e我们用$$$k$$$个点来表示一个图案,记为$$$\\{A_1,A_2,\\dots,A_k\\}$$$。要锁定智能手机的有效图案应满足以下条件:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 每个点最多被访问一次。也就是说,对于每个$$$1 \\le i \u0026lt; j \\le k$$$,$$$A_i \\neq A_j$$$。\u003c/li\u003e\u003cli\u003e 对于每个$$$1 \\le i \u0026lt; k$$$,连接$$$A_i$$$和$$$A_{i+1}$$$的线段不能穿过其他点。例如,$$$A_i\u003d(1,1),A_{i+1}\u003d(3,3)$$$是无效的,因为线段穿过了$$$(2,2)$$$。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e小兔子希望他的智能手机尽可能安全。因此,他需要一个\u003cspan class\u003d\"tex-font-style-bf\"\u003e强密码图案\u003c/span\u003e来锁定设备。强密码图案是符合一些额外条件的有效图案:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 每个点只被访问一次。也就是,$$$k\u003dn \\times m$$$。\u003c/li\u003e\u003cli\u003e 对于每个$$$1 \u0026lt; i \u0026lt;k$$$,由线段$$$A_iA_{i-1}$$$和线段$$$A_iA_{i+1}$$$形成的角必须是锐角(小于$$$90^\\circ$$$)。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e你能为他构建一个\u003cspan class\u003d\"tex-font-style-bf\"\u003e强密码图案\u003c/span\u003e吗?\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包含两个整数$$$n$$$和$$$m$$$($$$2 \\le n,m \\le 500$$$),表示网格的行数和列数。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出$$$n \\times m$$$行。第$$$i$$$行包含两个整数$$$x_i$$$和$$$y_i$$$($$$1 \\le x_i \\le n$$$,$$$1 \\le y_i \\le m$$$),表示图案的第$$$i$$$个点为$$$(x_i,y_i)$$$。\u003c/p\u003e\u003cp\u003e可以证明答案总是存在的。如果有多个答案,输出任意一个。\u003c/p\u003e"}},{"title":"示例","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 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\n2 1\n1 2\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e请注意,如果您的输出长度或格式与答案不匹配,您可能会收到演示错误的判决。\u003c/p\u003e"}}]}