{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLittle Tom loves playing games. One day he downloads a little computer game called \u0027Bloxorz\u0027 which makes him excited. It\u0027s a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/a29deb5841d183ca41249f35fe190549?v\u003d1713660582\"\u003e\u003cbr\u003eThe box stands on a single cell\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/16a2f00429bbb632a3e5088cf76415f1?v\u003d1713660582\"\u003e\u003cbr\u003eThe box lies on two neighbouring cells, horizontally\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/8ba09de5b29df1c037294d3d8afb6d92?v\u003d1713660582\"\u003e\u003cbr\u003eThe box lies on two neighbouring cells, vertically\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eAfter Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput contains multiple test cases. Each test case is one single stage of the game. It starts with two integers \u003ci\u003eR\u003c/i\u003e and \u003ci\u003eC\u003c/i\u003e(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains \u003ci\u003eR\u003c/i\u003e lines and \u003ci\u003eC\u003c/i\u003e characters for each line, with \u0027O\u0027 (Oh) for target cell, \u0027X\u0027 for initial position of the box, \u0027.\u0027 for a rigid cell, \u0027#\u0027 for a empty cell and \u0027E\u0027 for a easily broken cell. A test cases starts with two zeros ends the input.\u003c/p\u003e\u003cp\u003eIt guarantees that \u003c/p\u003e\u003cul\u003e\u003cli\u003eThere\u0027s only one \u0027O\u0027 in a plane.\u003c/li\u003e\u003cli\u003eThere\u0027s either one \u0027X\u0027 or neighbouring two \u0027X\u0027s in a plane.\u003c/li\u003e\u003cli\u003eThe first(and last) row(and column) must be \u0027#\u0027(empty cell).\u003c/li\u003e\u003cli\u003eCells covered by \u0027O\u0027 and \u0027X\u0027 are all rigid cells.\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test cases output one line with the minimum number of moves or \"Impossible\" (without quote) when there\u0027s no way to achieve the target cell. \u003c/p\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\u003e7 7\r\n#######\r\n#..X###\r\n#..##O#\r\n#....E#\r\n#....E#\r\n#.....#\r\n#######\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}