| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
When Taja runs out of money, she goes to the casino. Recently a new game appeared at the casino, and Taja wants to master it. Help her.
Two parties of the game are croupier and visitor of the casino. Croupier has a single regular $k$-faced dice, which has all integers from 1ドル$ to $k$ written on its faces. Croupier starts the game with rolling the dice once. Shown number determines amount of points gained by croupier.
To win, visitor has to gain more points, than croupier did. For this there's suggested a choice out of $n$ options. Each option is a pair: the dice and number of its allowed rolls. Each face of each dice has some number written on it. This dice is rolled required number of times, all shown numbers are summed up and this sum is exactly the points gained by a visitor.
But some faces, in addition to numbers, have bonus marks. If shown face has bonus mark, then corresponding amount of points is added to the total, and visitor get additional dice roll. All faces of the same dice are pairwise distinct, which means there's no two identical bonus faces and no two identical ordinary faces. Each dice has at least one face without bonus mark. For every dice, the probability of each of its face being shown is the same.
In this problem it is required that for each possible amount of croupier's points from 1ドル$ to $k$ you determine visitor's rolling option number, which leads to the maximal probability to gain stricly greater points than croupier did.
First line of the input contains single integer $n$ (2ドル \leq n \leq 10$) --- number of dice rolling options.
Next $n$ lines contain descriptions of options in the following format.
First number $c_i$ (1ドル \leq c_i \leq 10$) --- number of allowed rolls. Second number $f_i$ (2ドル \leq f_i \leq 12$) --- number of dice faces. Next $f_i$ numbers $v_{ij}$ --- numbers written on the faces. $v_{ij}$ is either simply a number from 1ドル$ to $f_i,ドル meaning amount of points, or it can have additional plus sign <<+>> (ASCII 43ドル$) in front of the number, which is the bonus mark. For every dice, its numbers without plus sign are unique, all numbers with plus sign are unique, and there's at least one face without bonus mark.
Last line contains single integer $k,ドル which always equals $\max\limits_{1 \leq i \leq n}$ ($c_i \times f_i$).
Output should contain $k$ lines, each of which contains single integer $b_i$ --- number of the best option, which will allow to win with maximal probability by gaining more than $i$ points (this probability shouldn't deviate from the right answer more than 10ドル^{-9}$).
Dice are numbered from 1ドル$ in the order thay are given in the input.
3 3 4 1 2 3 4 2 6 1 2 3 4 5 6 1 12 1 2 3 4 5 6 7 8 9 10 11 12 12
2 1 1 1 1 1 1 3 3 3 3 2
2 1 4 1 2 +1 +2 1 6 1 +1 2 3 4 5 6
2 2 2 2 1 1
Answer for the first sample could conain 1ドル$ on the first line, and the last could be any from 1ドル$ to 3ドル$.