Planete: Solving a Modular Equation System

You are given N records. Each record consists of two dates A_i and B_i (in the format MM/DD, without year) and an array of M integers a_i,1, a_i,2, …, a_i,M. First, convert each date to its day‐of‐year representation assuming January 1 is day 1 and December 31 is day 365. (For example, 01/01 is 1 and 12/31 is 365.)

For each record i (1 ≤ i ≤ N), you are to find an integer solution for variables x₁, x₂, …, x_M (with 1 ≤ x_j ≤ 365 for each j) satisfying the following system of congruences: \[ A_i + \sum_{j=1}^{M} a_{i,j} x_j \equiv B_i \pmod{365} \] Here, A_i and B_i represent the day‐of‐year values of the corresponding dates.

If a solution exists, output any one valid solution as M space‐separated integers. If no solution exists, output -1.

Note: All arithmetic is done modulo 365, where the conventional interpretation is applied (i.e. if a value is 365, it is equivalent to 0 modulo 365).

inputFormat

The first line contains two integers N and M, representing the number of records and the number of variables, respectively.

Then follow N lines. Each line contains two dates in the format MM/DD representing A_i and B_i, followed by M integers a_i,1, a_i,2, …, a_i,M separated by spaces.

outputFormat

If a solution exists, output one valid solution: M space‐separated integers (each in the range from 1 to 365). If no solution exists, output -1.

sample

1 1
01/01 01/02 1

1