{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cp\u003eIt was the last day of the summer camp you strayed into the labyrinth on the way to Komaba Campus, the University of Tokyo. \nThe contest has just begun.\nYour teammates must impatiently wait for you.\nSo you have to escape from this labyrinth as soon as possible.\u003cbr\u003e\n\nThe labyrinth is represented by a grid map.\nInitially, each grid except for walls and stairs is either on the first floor or on the second floor.\nSome grids have a switch which can move up or down some of the grids (the grids on the first floor move to the second floor, and the grids on the second floor to the first floor).\u003cbr\u003e\n\n In each step, you can take one of the following actions:\u003cbr\u003e\n\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cp\u003e Move to an adjacent grid (includes stairs) on the same floor you are now in.\n\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e Move to another floor (if you are in the stairs grid).\n\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e Operate the switch (if you are in a grid with a switch).\n\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003eLuckily, you have just found a map of the labyrinth for some unknown reason.\nLet\u0027s calculate the minimum step to escape from the labyrinth, and go to the place your teammates are waiting!\u003cbr\u003e\n\n\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe format of the input is as follows.\u003cbr\u003e\n\n\u003c/p\u003e\u003cblockquote\u003e\n\u003cvar\u003eW\u003c/var\u003e \u003cvar\u003eH\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eM\u003csub\u003e11\u003c/sub\u003eM\u003csub\u003e12\u003c/sub\u003eM\u003csub\u003e13\u003c/sub\u003e...M\u003csub\u003e1W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eM\u003csub\u003e21\u003c/sub\u003eM\u003csub\u003e22\u003c/sub\u003eM\u003csub\u003e23\u003c/sub\u003e...M\u003csub\u003e2W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e........\u003cbr\u003e\u003cvar\u003eM\u003csub\u003eH1\u003c/sub\u003eM\u003csub\u003eH2\u003c/sub\u003eM\u003csub\u003eH3\u003c/sub\u003e...M\u003csub\u003eHW\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eS\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e111\u003c/sub\u003eMS\u003csub\u003e112\u003c/sub\u003eMS\u003csub\u003e113\u003c/sub\u003e...MS\u003csub\u003e11W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e121\u003c/sub\u003eMS\u003csub\u003e122\u003c/sub\u003eMS\u003csub\u003e123\u003c/sub\u003e...MS\u003csub\u003e12W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e........\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e1H1\u003c/sub\u003eMS\u003csub\u003e1H2\u003c/sub\u003eMS\u003csub\u003e1H3\u003c/sub\u003e...MS\u003csub\u003e1HW\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e211\u003c/sub\u003eMS\u003csub\u003e212\u003c/sub\u003eMS\u003csub\u003e213\u003c/sub\u003e...MS\u003csub\u003e21W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e221\u003c/sub\u003eMS\u003csub\u003e222\u003c/sub\u003eMS\u003csub\u003e223\u003c/sub\u003e...MS\u003csub\u003e22W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e........\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003e2H1\u003c/sub\u003eMS\u003csub\u003e2H2\u003c/sub\u003eMS\u003csub\u003e2H3\u003c/sub\u003e...MS\u003csub\u003e2HW\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003eS11\u003c/sub\u003eMS\u003csub\u003eS12\u003c/sub\u003eMS\u003csub\u003eS13\u003c/sub\u003e...MS\u003csub\u003eS1W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003eS21\u003c/sub\u003eMS\u003csub\u003eS22\u003c/sub\u003eMS\u003csub\u003eS23\u003c/sub\u003e...MS\u003csub\u003eS2W\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e........\u003cbr\u003e\u003cvar\u003eMS\u003csub\u003eSH1\u003c/sub\u003eMS\u003csub\u003eSH2\u003c/sub\u003eMS\u003csub\u003eSH3\u003c/sub\u003e...MS\u003csub\u003eSHW\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\n\u003cp\u003eThe first line contains two integers \u003cvar\u003eW\u003c/var\u003e (\u003cvar\u003e3 ≤ W ≤ 50\u003c/var\u003e) and \u003cvar\u003eH\u003c/var\u003e (\u003cvar\u003e3 ≤ H ≤ 50\u003c/var\u003e). They represent the width and height of the labyrinth, respectively.\u003cbr\u003e\n The following \u003cvar\u003eH\u003c/var\u003e lines represent the initial state of the labyrinth.\nEach of \u003cvar\u003eM\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e is one of the following symbols:\u003cbr\u003e\n\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u0027#\u0027 representing a wall,\n\u003c/li\u003e\u003cli\u003e \u0027|\u0027 representing stairs,\n\u003c/li\u003e\u003cli\u003e \u0027_\u0027 representing a grid which is initially on the first floor,\n\u003c/li\u003e\u003cli\u003e \u0027^\u0027 representing a grid which is initially on the second floor,\n\u003c/li\u003e\u003cli\u003e a lowercase letter from \u0027a\u0027 to \u0027j\u0027 representing a switch the grid has, and the grid is initially on the first floor,\n\u003c/li\u003e\u003cli\u003e an uppercase letter from \u0027A\u0027 to \u0027J\u0027 representing a switch the grid has, and the grid is initially on the second floor,\n\u003c/li\u003e\u003cli\u003e \u0027%\u0027 representing the grid you are initially in (which is initially on the first floor) or\n\u003c/li\u003e\u003cli\u003e \u0027\u0026amp;\u0027 representing the exit of the labyrinth (which is initially on the first floor).\n\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003eThe next line contains one integer \u003cvar\u003eS\u003c/var\u003e (\u003cvar\u003e0 ≤ S ≤ 10\u003c/var\u003e), and then the following \u003cvar\u003eSH\u003c/var\u003e lines represent the information of the switches.\nEach of \u003cvar\u003eMS\u003csub\u003ekij\u003c/sub\u003e\u003c/var\u003e is one of:\u003cbr\u003e\n\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u0027#\u0027 if \u003cvar\u003eM\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e is a \u0027#\u0027,\n\u003c/li\u003e\u003cli\u003e \u0027|\u0027 if \u003cvar\u003eM\u003csub\u003eij\u003c/sub\u003e\u003c/var\u003e is a \u0027|\u0027,\n\u003c/li\u003e\u003cli\u003e \u0027*\u0027 if the grid is moved by the switch represented by the \u003cvar\u003ek\u003c/var\u003e-th alphabet letter, or\n\u003c/li\u003e\u003cli\u003e \u0027.\u0027 otherwise.\n\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003eNote that the grid which contains a switch may be moved by operating the switch.\nIn this case, you will move together with the grid.\u003cbr\u003e\nYou may assume each of the \u0027%\u0027 (start) and \u0027\u0026amp;\u0027 (goal) appears exacyly once, that the map is surround by walls, and that each alphabet in the map is any of the letters from \u0027A\u0027 (or \u0027a\u0027) to \u003cvar\u003eS\u003c/var\u003e-th alphabet letter.\u003cbr\u003e\n\n\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003ePrint the minimum step to reach the goal in one line.\nIf there is no solution, print \"-1\".\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e6 6\n######\n#_|A%#\n#B#_|#\n#^BBa#\n#B\u0026amp;A##\n######\n2\n######\n#*|*.#\n#.#.|#\n#*.**#\n#...##\n######\n######\n#*|*.#\n#*#.|#\n#..**#\n#..*##\n######\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e21\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e8 3\n########\n#%||Aa\u0026amp;#\n########\n2\n########\n#*||*..#\n########\n########\n#.||*.*#\n########\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e7\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e3 4\n###\n#%#\n#\u0026amp;#\n###\n0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e1\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 4\u003c/h2\u003e\n\n\u003cpre\u003e3 5\n###\n#%#\n#^#\n#\u0026amp;#\n###\n0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 4\u003c/h2\u003e\n\n\u003cpre\u003e-1\n\u003c/pre\u003e"}}]}