You are Ash, the famous Pokemon trainer. To become the greatest Pokemon master, you travel through regions battling against gym leaders and entering Pokemon League competitions. With your well- trained Pikachu, Squirtle and Bulbasaur, you have already captured six badges! What a marvellous performance! Now, you are walking through the Enchanted Forest, where the most powerful Pokemons live... No, not those giant dragons; we are actually talking about Jigglypuffs. A Jigglypuff is a normal-type Balloon Pokemon, with a round, balloon-like body, a tuft of fur on its forehead, and stubby arms and legs. What’s so powerful of them? Well, do you notice that microphone in the picture? That’s right, Jigglypuff has a well-regarded singing voice, and its most popular attack is to sing its opponent to sleep! Therefore, it is always a good idea to find a route avoiding places wherever you might hear the Jigglypuffs’ lullaby. Let us model the situation as follows: we shall treat the forest as a rectangular grid formed by paths which are 1 unit apart. Your starting position is at the top left corner of the grid (1, 1), and you will leave the forest at the lower right corner (R,C). There might be blocked areas which you are not allowed to tres- pass through. Jigglypuffs might be present at some intersections. The loudness L of each Jigglypuff is given, which means that places no more than L units away from the Jigglypuff are consid- ered “dangerous” and should be avoided. Input Input consists of several test cases. Each test begins with two integers R and C (1 ≤ R,C ≤ 200), the number of rows and columns in the grid map. Then comes an integer m, followed by m lines each giving the coordinates of a blocked position. Next there is an integer n (0 ≤ n ≤ 100), the number of Jigglypuffs in the forest. The following n lines each gives the position of a Jigglypuff and its loudness L (1 ≤ L ≤ 100). Input ends with a test case where R = 0 and C = 0. You must not process this test case. Output For each case, if some “dangerous” places are unavoidable, print ‘Impossible.’ Otherwise, give the length of the shortest path to get out of the forest safely. The figure on the right shows the sample test case. The area enclosed by the blue circle is “danger- ous”. The solution shown is unique. Sample Input 55 5 12 13 14 15 25
2/2 1 431 00 Sample Output 8