To encourage people to exercise more, the sports center in CD City, where Little Q lives, has a long-term points-for-gifts program.
The sports center offers many types of sports, each with a fixed non-negative integer point value. Participating in a sport once earns the corresponding points. The sports center introduces a new gift each month. When the total points for the month are greater than or equal to the points required for that month's gift, the points can be exchanged for a gift. Each month's gift can be redeemed multiple times, with the same number of points deducted each time. To encourage people to redeem prizes promptly, points earned each month can only be used within that month and cannot be carried over to the next.
Little Q is a fitness enthusiast whose hobby is inviting groups of friends to the sports center to participate in various sports. With the help of his friends, Little Q is able to redeem many gifts each month.
A new month is approaching, and Little Q has started planning his sports activities for the next month. However, Little Q discovered that the table where he recorded the points for each sport is missing. This table was something Little Q spent a year collecting, recording the points for all sports activities, large and small, at the sports center.
Extremely frustrated, Little Q suddenly remembered that he also had the habit of recording the number of times he participated in each sport every month. Later, he went to the sports center's website and found his remaining points for each month, which is the total points for that month minus the points required for the number of gifts he redeemed. As for how many gifts Little Q redeemed each month, he does not remember.
Little Q thought that he might be able to determine the points for each sport using this data. After some deduction, Little Q found that if a record for a certain month is incorrect, it is very likely that there will be no solution. Little Q participates in many sports each month, so it is normal to have made a mistake or two in his records.
Finally, Little Q came up with a compromise: find the points for each sport such that these points satisfy as many monthly records as possible.
Since Little Q has to go participate in sports today, this problem, like many others, is left to you, a student in informatics competitions.
Input
This is an answer-submission problem. All input data sports1.in ~ sports10.in are provided in the download files.
The first line of the input contains two positive integers $n$ and $m$, representing the number of sports and the number of months with records, respectively.
The next $m$ lines each contain $n + 2$ non-negative integers, representing a record for one month. The $i$-th number among the first $n$ numbers represents the number of times Little Q participated in the $i$-th sport that month, the $(n + 1)$-th number represents the points required to redeem one gift that month, and the $(n + 2)$-th number represents the remaining points after redeeming a certain number of gifts.
It is guaranteed that each number in the input does not exceed $2^{31} - 1$.
The end of the input file contains 8 lines, each containing an integer, which are the parameters $a_3, a_4, \dots, a_{10}$, the meanings of which are described in the scoring method.
Output
For the 10 given input files sports1.in ~ sports10.in, you need to submit your output files sports1.out ~ sports10.out respectively.
Each output file should contain $n$ lines, each containing a non-negative integer less than $10^{10m}$ (not exceeding $10m$ digits). The $i$-th line represents the points for the $i$-th sport.
Please note that for each test case, your output file must not exceed 1MB (1048576 bytes), otherwise the test case will be considered incorrect.
Examples
Input 1
2 4 2 0 4 2 0 2 3 1 5 7 24 16 2 0 4 5 2 2 1 1 0 0 0 0
Output 1
7 11
Note
Record 1: $2 \times 7 + 0 \times 11 = 14$, remaining 2 points after redeeming 3 prizes.
Record 2: $0 \times 7 + 2 \times 11 = 22$, remaining 1 point after redeeming 7 prizes.
Record 3: $5 \times 7 + 7 \times 11 = 112$, remaining 16 points after redeeming 4 prizes.
Record 4: Regardless of how the points for each sport are set, this record cannot be satisfied.
Scoring Method
For each data set, we have set 8 scoring parameters $a_3, a_4, \dots, a_{10}$. If the contestant's output is invalid, they receive zero points. Otherwise, let $w_{\text{user}}$ be the number of months satisfied by your solution, and $w_{\text{std}}$ be the number of months satisfied by our provided answer. Your score will be given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $w_{\text{std}} - w_{\text{user}} \leq a_{10}$ | 5 | $w_{\text{std}} - w_{\text{user}} \leq a_5$ |
| 9 | $w_{\text{std}} - w_{\text{user}} \leq a_9$ | 4 | $w_{\text{std}} - w_{\text{user}} \leq a_4$ |
| 8 | $w_{\text{std}} - w_{\text{user}} \leq a_8$ | 3 | $w_{\text{std}} - w_{\text{user}} \leq a_3$ |
| 7 | $w_{\text{std}} - w_{\text{user}} \leq a_7$ | 2 | $w_{\text{user}} \geq 0$ |
| 6 | $w_{\text{std}} - w_{\text{user}} \leq a_6$ | 1 | $w_{\text{user}} \geq 0$ |
If multiple conditions are met, the highest score among the satisfied conditions is taken.