{"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\"\u003eThe 15-puzzle has been around for over 100 years; even if you don\u0027t know it by that name, you\u0027ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let\u0027s call the missing tile \u0027x\u0027; the object of the puzzle is to arrange the tiles so that they are ordered as: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003e 1 2 3 4\u003cbr\u003e 5 6 7 8\u003cbr\u003e 9 10 11 12\u003cbr\u003e13 14 15 x\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003ewhere the only legal operation is to exchange \u0027x\u0027 with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle: \u003cbr\u003e\u003cpre\u003e\u003cbr\u003e 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4\u003cbr\u003e 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8\u003cbr\u003e 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12\u003cbr\u003e13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x\u003cbr\u003e r-\u0026gt; d-\u0026gt; r-\u0026gt;\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003eThe letters in the previous row indicate which neighbor of the \u0027x\u0027 tile is swapped with the \u0027x\u0027 tile at each step; legal values are \u0027r\u0027,\u0027l\u0027,\u0027u\u0027 and \u0027d\u0027, for right, left, up, and down, respectively. \u003cbr\u003e\u003cbr\u003eNot all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and \u003cbr\u003efrustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing \u0027x\u0027 tile, of course). \u003cbr\u003e\u003cbr\u003eIn this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three \u003cbr\u003earrangement.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus \u0027x\u0027. For example, this puzzle \u003cbr\u003e\u003cbr\u003e 1 2 3 \u003cbr\u003e x 4 6 \u003cbr\u003e 7 5 8 \u003cbr\u003e\u003cbr\u003eis described by this list: \u003cbr\u003e\u003cbr\u003e1 2 3 x 4 6 7 5 8\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"You will print to standard output either the word ``unsolvable\u0027\u0027, if the puzzle has no solution, or a string consisting entirely of the letters \u0027r\u0027, \u0027l\u0027, \u0027u\u0027 and \u0027d\u0027 that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.\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 3 4 1 5 x 7 6 8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eullddrurdllurdruldr\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}