{"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\u003eTheseus has just arrived to Crete to fight Minotaur. He found a labyrinth that has a form of a rectangular field of size \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e\u003c/span\u003e and consists of blocks of size \u003cspan class\u003d\"tex-span\"\u003e1 × 1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eEach\u003c/span\u003e block of the labyrinth has a button that rotates \u003cspan class\u003d\"tex-font-style-bf\"\u003eall\u003c/span\u003e blocks \u003cspan class\u003d\"tex-span\"\u003e90\u003c/span\u003e degrees clockwise. Each block rotates around its center and doesn\u0027t change its position in the labyrinth. Also, each block has some number of doors (possibly none). In one minute, Theseus can either push the button in order to rotate all the blocks \u003cspan class\u003d\"tex-span\"\u003e90\u003c/span\u003e degrees clockwise or pass to the neighbouring block. Theseus can go from block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to some neighbouring block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e only if block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e has a door that leads to block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e and block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e has a door that leads to block \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTheseus found an entrance to labyrinth and is now located in block \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e\u0026nbsp;— the block in the row \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and column \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Theseus know that the Minotaur is hiding in block \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e and wants to know the minimum number of minutes required to get there.\u003c/p\u003e\u003cp\u003eTheseus is a hero, not a programmer, so he asks you to help him.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 1000\u003c/span\u003e)\u0026nbsp;— the number of rows and the number of columns in labyrinth, respectively.\u003c/p\u003e\u003cp\u003eEach of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e characters, describing the blocks of the labyrinth. The possible characters are:\u003c/p\u003e\u003cul\u003e \u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e doors (one door to each neighbouring block); \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e doors\u0026nbsp;— to the left and to the right neighbours; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e|\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e doors\u0026nbsp;— to the top and to the bottom neighbours; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e^\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e door\u0026nbsp;— to the top neighbour; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u0026gt;\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e door\u0026nbsp;— to the right neighbour; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u0026lt;\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e door\u0026nbsp;— to the left neighbour; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003ev\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e door\u0026nbsp;— to the bottom neighbour;\u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e doors\u0026nbsp;— to all neighbours except left one; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e doors\u0026nbsp;— to all neighbours except right one; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003eU\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e doors\u0026nbsp;— to all neighbours except top one; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003eD\u003c/span\u003e» means this block has \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e doors\u0026nbsp;— to all neighbours except bottom one;\u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-font-style-tt\"\u003e*\u003c/span\u003e» means this block is a wall and has no doors. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eLeft, right, top and bottom are defined from representing labyrinth as a table, where rows are numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e from top to bottom and columns are numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e from left to right.\u003c/p\u003e\u003cp\u003eNext line contains two integers\u0026nbsp;— coordinates of the block \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e), where Theseus is initially located.\u003c/p\u003e\u003cp\u003eLast line contains two integers\u0026nbsp;— coordinates of the block \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e), where Minotaur hides.\u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that both the block where Theseus starts and the block where Minotaur is hiding have at least one door. Theseus and Minotaur may be initially located at the same block.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf Theseus is not able to get to Minotaur, then print \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e in the only line of the output. Otherwise, print the minimum number of minutes required to get to the block where Minotaur is hiding.\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\u003e2 2\n+*\n*U\n1 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\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\u003e2 3\n\u0026lt;\u0026gt;\u0026lt;\n\u0026gt;\u0026lt;\u0026gt;\n1 1\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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\u003eAssume that Theseus starts at the block \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e at the moment \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e.\u003c/p\u003e"}}]}