{"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\u003eAllen dreams of one day owning a enormous fleet of electric cars, the car of the future! He knows that this will give him a big status boost. As Allen is planning out all of the different types of cars he will own and how he will arrange them, he realizes that he has a problem. \u003c/p\u003e\u003cp\u003eAllen\u0027s future parking lot can be represented as a rectangle with $$$4$$$ rows and $$$n$$$ ($$$n \\le 50$$$) columns of rectangular spaces, each of which can contain at most one car at any time. He imagines having $$$k$$$ ($$$k \\le 2n$$$) cars in the grid, and all the cars are initially in the second and third rows. Each of the cars also has a different designated parking space in the first or fourth row. Allen has to put the cars into corresponding parking places.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"340px\" src\u003d\"CDN_BASE_URL/f6a11c6621db004154313fae40650ee9?v\u003d1726342269\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"491px\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eIllustration to the first example.\u003c/span\u003e \u003c/center\u003e\u003cp\u003eHowever, since Allen would never entrust his cars to anyone else, only one car can be moved at a time. He can drive a car from a space in any of the four cardinal directions to a neighboring empty space. Furthermore, Allen can only move one of his cars into a space on the first or fourth rows if it is the car\u0027s designated parking space. \u003c/p\u003e\u003cp\u003eAllen knows he will be a very busy man, and will only have time to move cars at most $$$20000$$$ times before he realizes that moving cars is not worth his time. Help Allen determine if he should bother parking his cars or leave it to someone less important.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \\le n \\le 50$$$, $$$1 \\le k \\le 2n$$$), representing the number of columns and the number of cars, respectively.\u003c/p\u003e\u003cp\u003eThe next four lines will contain $$$n$$$ integers each between $$$0$$$ and $$$k$$$ inclusive, representing the initial state of the parking lot. The rows are numbered $$$1$$$ to $$$4$$$ from top to bottom and the columns are numbered $$$1$$$ to $$$n$$$ from left to right.\u003c/p\u003e\u003cp\u003eIn the first and last line, an integer $$$1 \\le x \\le k$$$ represents a parking spot assigned to car $$$x$$$ (you can only move this car to this place), while the integer $$$0$$$ represents a empty space (you can\u0027t move any car to this place).\u003c/p\u003e\u003cp\u003eIn the second and third line, an integer $$$1 \\le x \\le k$$$ represents initial position of car $$$x$$$, while the integer $$$0$$$ represents an empty space (you can move any car to this place).\u003c/p\u003e\u003cp\u003eEach $$$x$$$ between $$$1$$$ and $$$k$$$ appears exactly once in the second and third line, and exactly once in the first and fourth line.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf there is a sequence of moves that brings all of the cars to their parking spaces, with at most $$$20000$$$ car moves, then print $$$m$$$, the number of moves, on the first line. On the following $$$m$$$ lines, print the moves (one move per line) in the format $$$i$$$ $$$r$$$ $$$c$$$, which corresponds to Allen moving car $$$i$$$ to the neighboring space at row $$$r$$$ and column $$$c$$$.\u003c/p\u003e\u003cp\u003eIf it is not possible for Allen to move all the cars to the correct spaces with at most $$$20000$$$ car moves, print a single line with the integer $$$-1$$$.\u003c/p\u003e"}},{"title":"Examples","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\u003e4 5\n1 2 0 4\n1 2 0 4\n5 0 0 3\n0 5 0 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 1 1\n2 1 2\n4 1 4\n3 4 4\n5 3 2\n5 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e1 2\n1\n2\n1\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e1 2\n1\n1\n2\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 1 1\n2 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample test case, all cars are in front of their spots except car $$$5$$$, which is in front of the parking spot adjacent. The example shows the shortest possible sequence of moves, but any sequence of length at most $$$20000$$$ will be accepted.\u003c/p\u003e\u003cp\u003eIn the second sample test case, there is only one column, and the cars are in the wrong order, so no cars can move and the task is impossible.\u003c/p\u003e"}}]}