Description
"Go Down Chicken is a vicious monster, it will hit you until you have cerebral concussion(腦震盪)." ~from an anonymous bestiary.
To avoid from being attacked by Go Down Chicken, you need to solve the following problem.
This question has multiple input in each testcase. The input end with EOF.
Each input contain n numbers ai(1 <= i <= n) and q queries xj(1 <= j <= q).
Each number ai represents a game.
The game is that you need to fill a 3 * ai tiles with the shape(The left one) described in the picture below.
The shape can't overlap and no empty space allow. For each ai you need to calculate how many ways you can fill the tiles.
The number of ways may be very large, therefore you need to mod the answer with 1000000007.
For example:
The picture above present a 3*6 tiles, you will have 8 ways to fill the tiles with the shape.
Once you finish those n games, you need to answer q queries.
Each query will give you one integer xj means the ways to fill the tiles.
You need to answer xj is in which round of the games?
If there're multiple answers, answer the earliest round.
If you can't find the answer, print "Go Down Chicken 404"
Sample input explain:
You have n = 5, q = 3
Then you have 5 integer: 6, 9, 13, 4, 3
If the tiles is 3*6: you have 8 ways to fill it.
If the tiles is 3*9: you have 0 ways to fill it.
If the tiles is 3*13: you have 0 ways to fill it.
If the tiles is 3*4: you have 4 ways to fill it.
If the tiles is 3*3: you have 0 ways to fill it.
Then you have 3 queries: 0, 4, 1024
There are multiple rounds turn out have 0 ways, but you need to answer the earliest round. The earliest round is second round.
Therefore the answer is 2.
The round that turns out have 4 ways is the forth round.
Therefore the answer is 4.
The round that turns out have 1024 ways can't be found.
Therefore the answer is "Go Down Chicken 404".
Input
The input is end with EOF
Each input contains several lines.
First line contains two integer n(1 <= n <= 1000000), q( 1 <= q <= 1000000).
Second line contain n integer ai( 1 <= ai <= 1000000).
Each ai is followed by a symbol "(/`A`)/ ~I__I" and separated by a blank from the next integer.
The following q lines each line contains one integer xj .
Output
For each query print that xj is the result of which round of the games(start from 1).
If there're multiple answers, answer the earliest round.
If you can't find the answer, print "Go Down Chicken 404"