시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 223 32 23 13.068%

문제

상근이의 가구 공장에서 일하는 사람은 총 m명이다. 모든 직원은 동등한 기술 능력을 가지고 있고, 동일한 생산성을 가진다. 다음달에 만들어야 하는 가구 총 n개이고, 상근이는 다음달 생산 계획을 세우려고 한다.

각각의 가구 i는 시작할 수 있는 가장 이른 시간 si, 제작 시간 wi, 마감 시간 di를 가지고 있다. 즉, 각 가구 i에 대해서 일을 시작할 수 있는 가장 빠른 시간은 si이고, 완성을 하는데 wi만큼 시간이 걸리고, di 또는 그 전에 가구를 완성해야 한다. (di ≥ si + wi)

각 가구를 작업할 수 있는 직원의 수는 한 명이다. 중간에 작업을 멈추고, 다른 가구를 작업하는 것도 가능하다. 잠시 멈춘 작업은 다른 사람이 이어서 할 수도 있다. 모든 직원은 일을 정수 시간일 때 시작하고 끝낸다. 편의상 시간은 1, 2, 3, ..., max{di}로 나타낸다.

모든 가구를 마감 시간 전에 완성하는 다음달 생산 계획을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 직원의 수 m과 만들어야 하는 가구의 수 n이 주어진다. (1 ≤ m ≤ 10, 1 ≤ n ≤ 100) 다음 n개 줄에는 각 가구의 정보 si, wi, di (1 ≤ si < di ≤ 500, 1 ≤ wi ≤ di-si)가 주어진다.

출력

각 테스트 케이스마다 n줄을 출력한다. i번째 줄에는 i번 가구의 제작 스케줄을 나타내는 홀수개의 정수 "k, a1, b1, a2, b2, ..., ak, bk"를 출력해야 한다. k는 시간 구간의 수를 나타내며, (aj, bj)는 aj부터 bj까지 한 직원이 그 가구를 제작한다는 뜻이다. (ai < bi < ai+1을 만족해야 한다) 만약, 모든 가구를 완성하는 계획을 세울 수 없는 경우에는 0을 출력한다.

예제 입력

2
2 4
2 2 5
1 5 8
4 2 6
3 3 7
1 3
2 4 7
3 1 5
4 2 6

예제 출력

1 2 4
3 1 3 4 5 6 8
1 4 6
2 3 4 5 7
0

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 E번