Problem Description

Translated from COCI 2009.12 T6 “PLANETE”.

You are given $N$ records. The $i$-th record contains two dates $A_i, B_i$ without a year (in other words, only month and day), and an array $a_{i,1}, a_{i,2}, \dots, a_{i,M}$ of length $M$. Find any solution to the system of equations in $x_1, x_2, \dots, x_M\ (1 \le x_j \le 365)$:

$\begin{cases}A_1+\displaystyle\sum_{j=1}^M a_{1,j}x_j\equiv B_1\pmod{365} \\ A_2+\displaystyle\sum_{j=1}^M a_{2,j}x_j\equiv B_2\pmod{365} \\ \vdots \\ A_N+\displaystyle\sum_{j=1}^M a_{N,j}x_j\equiv B_N\pmod{365}\end{cases}$

If there is no solution, output -1 only.

Input Format

The first line contains two integers $N, M$.

In the next $N$ lines, the $i$-th line starts with four integers, representing: the day of $A_i$, the month of $A_i$, the day of $B_i$, and the month of $B_i$. Then follow $M$ integers representing $a_{i,1}, a_{i,2}, \dots, a_{i,M}$.

Output Format

If there is a solution, output $M$ lines in total. The $i$-th line contains one integer, representing $x_i$.

If there is no solution, output -1 only.

1 1
26 02 03 03 1

5

1 1
26 02 03 03 2

185

3 3
22 03 01 10 9 10 10
05 05 16 12 1 7 10
20 06 15 01 4 9 10

102
204
125

Hint

Constraints: $1 \le N, M \le 200$, $0 \le a_{i,j} \le 200$. The input months and days are guaranteed to be valid.

Translated by ChatGPT 5