Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Chess Game
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1183Accepted: 402

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.

Sample Input

10
1
9 2
2
2 4
4 4
1
5

Sample Output

8.81

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator