{"trustable":false,"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":"MD","content":"Chtholly 有一个 $n\\times m$ 的迷宫,每个格子有通向其他格子的门,每秒她可以把全部房间顺时针旋转 $90$ 度或者移动到相邻的房间,但前提是两个房间之间都有门,问 Chtholly 从 $(x_s,y_s)$ 到 $(x_t,y_t)$ 最少花费的时间。"}},{"title":"Input","value":{"format":"MD","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\n\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\n\u003cul\u003e \n \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\n \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\n \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\n \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\n \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\n \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\n \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\n \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\n \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\n \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\n \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\n \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\n\u003c/ul\u003e\n\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\n\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\n\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\n\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":"MD","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":"Sample 1","value":{"format":"MD","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":"Sample 2","value":{"format":"MD","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":"MD","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"}}]}