URI Online Judge | 1597

Unmasking the Sultan's Employee

By Gabriel R. C. Peixoto Brazil

Timelimit: 2

A Sultan was wary of his employee. He claimed that he worked forever, without stopping, to fulfill his tasks of N different kinds. The sultan wants to know exactly how long it takes to complete each one of the jobs, to better evaluate if the employee is lazy or really overloaded.

To try to unmask the employee he started to request reports from his activities. The employee delivered N different reports, the same amount of the total of tasks, what let the sultan more and more wary. This employee works in journeys of P hours and each task takes between one and P hours to complete. All the tasks take an entire quantity of hours to complete them.

The working hours happen in P early hours.

Each report consists of the time which the employee started and finished working, relatively to the beginning of the expedient. That is, if he claims that he started to work in the hour 1 then he worked on the tasks on the report in the beginning of the expedient and if he claims that he stopped working in the hour 3 then he stopped in the end of this hour, working 3 hours in this period.

The employee did not write down the day I started working and the day it ended. The schedules of the report does not always refer to the same day. In this case the employee claims that stopped working at the end of the workday and reinicionou the task early next day. In the previous example, the employee could have worked 4 hours, P + 4 hours, 2P + 4 hours, etc. With reports indicating that the employee started work at 3 pm and ended at 2 are perfectly valid.

                    

In addition to this information, each report contains how many of each type tasks were completed. During this period, the employee claims to have worked nonstop.

                                         

Your task is, given the reporting information, determine the duration in hours of each task, if that is possible.

Input

The input consists in several instances and ends with end of file(EOF).

The first line of each instance contains two integers, N (1 ≤ N ≤ 100) and P (2 ≤ P ≤ 24, P is a prime number). The next N lines contain N + 2 integers each one. The i-th line, from those N lines, corresponds to the i-th report and consists of Si , Ti (1 ≤ Si, TiP) , Ai,1 , . . . , Ai,N. Where Si and Ti corresponds, respectively, to the time in that the employee started and finished working. Each Ai,j (0 ≤ Ai,j ≤ 109 and ΣjAi,j > 0) is the number of times that the task j was realized during the time of the report i.

Output

For each instance print only one line in the output, which consists of:

Sample Input Sample Output

3 23
1 5 5 0 0
3 6 0 0 1
0 22 3 2 2
2 7
1 2 1 0
2 5 1 0
2 13
1 3 1 1
1 6 2 2

1 6 4
-1
-2