#P3756. Chess Game

Chess Game

Description

There is a kind of chessboard-game which should be played with pure luck. It is always welcomed by children and maybe some teenagers enjoy killing-time with it. The rules of the game are easy to understand. Totally there are N grids on a chessboard with numeric order. The players start their journeys at grid 0. At the beginning of each round, the player will roll a dice to decide how many steps he will go forward. After he has arrived at the target place, he may found some instructions to follow: he might be told to go forward several steps, or to go backward several steps, or he would be asked to have a rest, with no right to roll the dice in the next round. The target of such game is quite simple, too: try to be the first player who reaches the goal!

For university students, such games looks too simple, or sometimes naïve, but now this game has one more application—to evaluate one's RP (which is a very important property in our daily life)! In order to decide whether you have high RP or not, it is quite essential to decide the expectation number of the rounds you can reach the goal, and that is what you should do.

To remove ambiguities, we made the following assumptions:

1) Only one instruction should be followed and there is no chain-effect for instructions. For example, if you followed the instruction on grid 15 and go 3 steps forward to grid 18, then you will wait at grid 18 until the next round begins no matter what instructions are in grid 18.

2) One can reach the goal if and only if he arrived exactly on grid N and redundant steps will change directions. For example, the goal is at grid 100 and you are now standing in grid 98, if you roll the dice and get 5 points, then your finally position is in grid 97(98->99->100->99->98->97) if there is no instructions at grid 97. The same rule is adapted to grid 0.

3) The dice is a cube and the probability of getting every kind of points from 1 to 6 is equal to 1/6.

4) There are 3 kind of instructions, go forward for 1 to 6 steps/go backward for 1 to 6 steps/no dice rolling in the next round.

Input the information of the chessboard and you should output the expectation number of the rounds you can reach the goal.

Input

The first line of the input contains one integer N(N ≤ 100), the number of grids on the chessboard (so that there are N+1 grids totally).

The next line contains one integer Nf, the number of "go forward" instructions. Next Nf lines contain two integers each. The first integer stands for the number of grid having the instruction and the second integer stand for the number of steps to go forward.

Following line contains one integer Nb, the number of "go backward" instructions. The formats of next Nb lines are similar as what mentioned above.

The next line contains one integer Ns, the number of "stop" instructions. Next Ns lines contain one integer each, which stand for the number of grid having the instruction.

Output

Output contains only one real number, representing the expectation number of the rounds to reach the goal. The answer should be rounded to 0.01. If it is impossible to reach the goal, print "Impossible" instead.

10
1
9 2
2
2 4
4 4
1
5
8.81

Source

POJ Monthly Contest - 2010.04.04, Mars