{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA zoology research lab has a terrarium with rare species of snakes. Terrarium is a flat box filled with soil, and has a glass top allowing to watch the snakes. There are trenches in the soil, and snakes constantly move along the trenches. All snakes have diameter of 1 cm and integer length of no less than 2 cm.\u003c/p\u003e\u003cp\u003eWhile watching the snakes, the zoologists discovered a pattern in their movement: each snake moves at a speed of 1 cm per second forward, until it encounters either a wall or another snake. Faced an obstacle, snake first tries to turn right, if there is also obstacle on the right, then it tries to turn left. If there is obstacle on the left also, the snake waits for a second before trying to move again.\u003c/p\u003e\u003cp\u003eIn order to validate the discovery, it was decided to write a program that simulates snakes\u0027 behaviour. This task was assigned to you.\u003c/p\u003e\u003cp\u003eThe terrarium is represented by an array of \u003ci\u003eN\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e characters. Each character is one of:\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u0027.\u0027 (ASCII 46) — trench\u003c/li\u003e\u003cli\u003e\u0027#\u0027 (ASCII 35) — wall\u003c/li\u003e\u003cli\u003e\u0027A\u0027 to \u0027Z\u0027 — snake\u0027s head\u003c/li\u003e\u003cli\u003e\u0027a\u0027 to \u0027z\u0027 — snake\u0027s body or tip of the tail\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eSnakes are represented by Latin letters, so there are no more than 26 snakes in terrarium. Snakes try to move in alphabetical order every second.\u003c/p\u003e\u003cp\u003eYour program must output the state of the terrarium after \u003ci\u003eT\u003c/i\u003e seconds.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst line of input file contains integers \u003ci\u003eN\u003c/i\u003e \u003ci\u003eT\u003c/i\u003e. Following \u003ci\u003eN\u003c/i\u003e lines contain \u003ci\u003eN\u003c/i\u003e characters each — the initial state of the terrarium. The input file guarantees unambiguous recognition of snakes — all snakes are continuous, every character of snake\u0027s body has exactly two neighbour characters belonging to the same snake, while head and tip of the tail have exactly one.\u003c/p\u003e\u003cp\u003e\u003cb\u003eConstraints\u003c/b\u003e\u003c/p\u003e\u003cp\u003e2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 1000, 1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput file must contain \u003ci\u003eN\u003c/i\u003e lines of \u003ci\u003eN\u003c/i\u003e characters — the state of the terrarium after \u003ci\u003eT\u003c/i\u003e seconds.\u003cbr\u003e \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\u003e\u003cb\u003eSample input 1\u003c/b\u003e\r\n4 8\r\n.bB.\r\n....\r\na.#.\r\naaA.\r\n\u003cb\u003eSample input 2\u003c/b\u003e\r\n7 100000\r\naA.....\r\na#####D\r\naa....d\r\n......d\r\n......d\r\n......d\r\n.......\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cb\u003eSample output 1\u003c/b\u003e\r\n.baa\r\n.BAa\r\n..#.\r\n....\r\n\u003cb\u003eSample output 2\u003c/b\u003e\r\naaaaADd\r\n.#####d\r\n......d\r\n......d\r\n.......\r\n.......\r\n.......\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Bold texts appearing in the sample sections are informative and do not form part of the actual data."}}]}