{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"We have arrived at the age of the Internet. Many software applications have transformed from stand-alone to online applications. Computer games are following this trend as well. Online games are becoming more and more popular, not only because they are more intelligent, but also because they can bring great profits. \"The computer game industry is developing rapidly in China. Online game revenues amounted to 1.3 billion Yuan last year and are expected to reach 6.7 billion Yuan by 2007.\" reported by China Daily in 2004.\r\u003cbr\u003eHowever, good games originate from good programmers. We take for example that there is a RPG (Role Playing Game) and your boss asks you to implement some tasks. For simplicity’s sake, we assume there are two kinds of roles in this game: one is player and the other is monster. You should help the player to achieve the goal: reach the place where treasure is positioned as early as possible and get the treasure. \r\u003cbr\u003eThe map of the game is a matrix of N * M identical cells. Some cells are passable blocks, and others are non-passable rocks. At any time, there is at most one role occupying a block.\r\u003cbr\u003eAt the beginning, the time is set to 0, and the player is at a certain block. He then moves towards the treasure. At each turn, we have some rules:\r\u003cbr\u003e\u003cul\u003e\u003cli\u003eThe player can stay in the same block during the next one-second time duration, or he can walk or run towards the east, south, west, north, northeast, northwest, southeast, and southwest.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eWith walking, the player can arrive at the corresponding passable blocks around him (See Fig.1). Each move takes 1 second. \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eWith running, the player can arrive at the corresponding passable blocks 2 cells away from him (See Fig.2). Each run takes 1 second. As demonstrated in Fig.3, if a neighbor cell is not passable, the player cannot run in that direction. For example, if cell 2 is a rock, running from 1 to 3 is impossible. \r\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/fa65b76deef8bacad158c5ba7a39c3e3?v\u003d1714463569\"\u003e\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eThe monsters are classified into aggressive and non-aggressive. If a monster occupies a cell, the player cannot move into that cell or run through that cell. In addition, the player cannot move into the cells surrounding an aggressive monster, because it will attack the player near it. For example, in Fig.4, if there is an aggressive monster in 5, then the cell 1, 2, 3, 4, 6, 7, 8 and 9 are in its attacking region, so the player cannot stay in or pass through these cells.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eMonsters change their positions each turn. Each monster appears by its position sequence iteratively. That\u0027s to say, given the position sequence of monster i: (x1, y1), (x2, y2), ..., (xs, ys), its initial position is (x1, y1) at time 0, then it appears in (x2, y2) at time 1, and so on. When monster i arrives at (xs, ys) at time s-1, it will arrive in (x1, y1) at time s, and start to repeat.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eAt the start of each turn, all the monsters change their positions first (the way of changing is given above). If a monster appears in the player\u0027s cell, or if an aggressive monster appears near the player to put him in its attacking region, the player will die, and the goal cannot be achieved. After all the monsters change their positions, the player makes a move or stays in the same cell. In his move, the moving path should not be occupied by any rocks or monsters or in the attacking region of any aggressive monsters. When counting the total time, we can neglect the time between monsters\u0027 position change and the player\u0027s move.\u003c/li\u003e\u003c/ul\u003e\r\u003cbr\u003eGiven the map of the game, the player\u0027s starting position, the treasure position and all the monsters\u0027 positions in every second, your task is to write a program to find the minimum time that the player gets the treasure."}},{"title":"Input","value":{"format":"HTML","content":"The input consists of several test cases. The first line of each case contains two integers N and M (1 \u0026lt;\u003d N, M \u0026lt;\u003d 100), where N is the height of the map and M is the width of the map. This is followed by N lines each containing M characters representing the map. A \u0027#\u0027 represents a rock, a \u0027.\u0027 is a free block, \u0027p\u0027 is the starting position of the player, \u0027t\u0027 is the position of the treasure, \u0027n\u0027 is the initial position of a non-aggressive monster, and an \u0027a\u0027 stands for the initial position of an aggressive monster.\r\u003cbr\u003eThe cell (i, j) is the j-th cell on the i-th row counting from left to right. The rows are counted from 1 to N starting from the first line of the matrix. We can number all the monsters as 1, 2, 3… according to their initial position, sorting first by row, then by column.\r\u003cbr\u003eThe (n+2)-th line contains an integer p (0 \u0026lt;\u003d p \u0026lt;\u003d 100), which is the total number of monsters (i.e. the total number of \u0027n\u0027s and \u0027a\u0027s in the matrix). It is followed by p lines each specifying a monster\u0027s position sequence in the following format: the i-th (1 \u0026lt;\u003d i \u0026lt;\u003d p) line corresponds to monster i, which begins with an integer s (1 \u0026lt;\u003d s \u0026lt;\u003d 100), meaning the length of position sequence. Then s pairs of integers x1, y1, x2, y2, …, xs, ys are followed, separated by blanks. Each pair is a free block in the map, (i.e. a monster never goes to a rock cell). \r\u003cbr\u003eIt is assured that none of the aggressive monsters\u0027 initial position is around the player. Two consecutive cases are separated by a blank line. The input is terminated by a line containing a pair of zeros.\r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the minimum total time required for the player to get the treasure, in seconds. If it\u0027s not possible to get the treasure, or the minimum required time is greater than 100 seconds, please print a line just containing the string \"impossible\". Two consecutive cases should be separated by a blank line."}},{"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 8\r\n#.#####.\r\n#.t#..p.\r\n#..#....\r\n..#a.#.#\r\n#...##.n\r\n.#......\r\n........\r\n2\r\n2 4 4 5 4\r\n3 5 8 6 8 5 7\r\n\r\n3 3\r\np#.\r\n##.\r\nt..\r\n0\r\n\r\n2 2\r\n#t\r\np#\r\n0\r\n\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n\r\nimpossible\r\n\r\n1\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":"In the first sample case, the player can follow (2,7), (4,7), stay in (4,7), (6,7), (7,6), (7,4), (5,2), (3,2) and (2,3) to get the treasure with the minimum time (8 seconds). "}}]}