시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 0 0 0.000%

문제

동혁 천문 관측소에서는 망원경 N개로 서로 다른 행성을 관측하고 있다. 관측소에서는 행성에서 발생하는 사건을 M가지 종류로 구분해 놓았다. 모든 행성에서 하루에 발생하는 사건은 한 종류이다. 모든 사건은 적어도 하루동안 지속되며, 많아야 365일동안 지속된다. 사건은 발생했다면, 항상 하루 종일 발생한다. 즉, 첫 날 지속되고, 둘째 날의 중간에 사건이 그만 발생하는 경우는 없다. 둘째 날에도 사건이 발생했다면, 둘째 날이 끝날 때 까지 사건이 발생한다. 각 사건은 항상 같은 기간 동안 발생한다. 즉, 어떤 행성이서 발생하느냐에 상관 없이 사건의 종류가 같다면 일어나는 기간도 같다.

이제 몇 년 동안 관측한 데이터를 분석하려고 한다. 망원경은 모든 관측을 기록해두었다. 하지만, 기록한 연도를 적지 않았다. 각 망원경이 기록한 내용은 기록을 시작한 날짜와, 끝낸 날짜, 그리고 각 사건이 몇 종류 발생했는지 기록되어 있다. 이 때, 각 사건이 발생하는 기간을 구하는 프로그램을 작성하시오.

일년은 365일이고, 윤년은 없다.

입력

첫째 줄에 망원경의 수 N과 종류의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

다음 N개 줄에는 아래 형식과 같은 M+4개의 숫자가 주어진다.

D1D1 M1M1 D2D2 M2M2 F1 F2 ... FM

여기서 D1D1 M1M1 (01 ≤ DD ≤ 31, 01 ≤ MM ≤ 12)은 관측을 시작한 날짜이고, D2D2 M2M2는 끝난 날짜이다. 그리고, Fi (0 ≤ Fi ≤ 200)는 사건 i가 발생한 횟수이다.

출력

출력은 총 M개 숫자이고, 각 사건이 발생한 기간이다. 만약, 가능한 정답이 여러가지라면 아무거나 출력한다. 또, 정답이 없는 경우에는 -1을 출력한다.

예제 입력

1 1
26 02 03 03 1

예제 출력

5

힌트