Donghyuk Astronomical Observatory

The Donghyuk Astronomical Observatory uses N telescopes to observe different planets. The observatory classifies planetary events into M types. On every planet, exactly one event type occurs each day. Once an event starts, it lasts only in whole-day units, for at least 1 day and at most 365 days.

An event type always has the same duration. In other words, if two occurrences have the same type, they last for the same number of days no matter which planet they occur on.

The observatory now wants to analyze data collected over several years. Each telescope kept a record, but the year was not written down. For each telescope, the record contains the date observation started, the date observation ended, and how many times each event type occurred during that observation.

Write a program that finds the duration of each event type. A year has 365 days, and there are no leap years.

The first line contains the number of telescopes N and the number of event types M. (1 <= N, M <= 200)

Each of the next N lines contains M + 4 integers in the following format.

D1 M1 D2 M2 F1 F2 ... FM

D1 M1 is the date when observation started, and D2 M2 is the date when observation ended. Dates are given as day then month, with 01 <= D <= 31 and 01 <= M <= 12. Fi (0 <= Fi <= 200) is the number of times event type i occurred.

Print M integers, one per line. The i-th integer must be the duration of event type i.

If there are multiple possible answers, print any one of them. If no answer is possible, print -1.