시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 304 56 36 15.929%

문제

상근이의 가구 공장에서 일하는 사람은 총 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을 출력한다.

예제 입력 1

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

1 2 4
3 1 3 4 5 6 8
1 4 6
2 3 4 5 7
0
W3sicHJvYmxlbV9pZCI6Ijg5MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWFkNmMgXHVhY2Y1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVhYzAwXHVhZDZjIFx1YWNmNVx1YzdhNVx1YzVkMFx1YzExYyBcdWM3N2NcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2QxZCBtXHViYTg1XHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzQwIFx1YjNkOVx1YjRmMVx1ZDU1YyBcdWFlMzBcdWMyMjAgXHViMmE1XHViODI1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWMwZGRcdWMwYjBcdWMxMzFcdWM3NDQgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWIyZWNcdWM1ZDAgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjMDBcdWFkNmMmbmJzcDtcdWNkMWQgblx1YWMxY1x1Yzc3NFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YjJlYyBcdWMwZGRcdWMwYjAgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzEzOFx1YzZiMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjMDBcdWFkNmMmbmJzcDtpXHViMjk0IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3NzRcdWI5NzggXHVjMmRjXHVhYzA0IHM8c3ViPmk8XC9zdWI+LCBcdWM4MWNcdWM3OTEgXHVjMmRjXHVhYzA0IHc8c3ViPmk8XC9zdWI+LCBcdWI5YzhcdWFjMTAgXHVjMmRjXHVhYzA0IGQ8c3ViPmk8XC9zdWI+XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1YWMwMFx1YWQ2YyBpXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3N2NcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDAgczxzdWI+aTxcL3N1Yj5cdWM3NzRcdWFjZTAsIFx1YzY0NFx1YzEzMVx1Yzc0NCBcdWQ1NThcdWIyOTRcdWIzNzAgdzxzdWI+aTxcL3N1Yj5cdWI5Y2NcdWQwN2MgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YWNlMCwgZDxzdWI+aTxcL3N1Yj4gXHViNjEwXHViMjk0IFx1YWRmOCBcdWM4MDRcdWM1ZDAgXHVhYzAwXHVhZDZjXHViOTdjIFx1YzY0NFx1YzEzMVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChkPHN1Yj5pPFwvc3ViPiAmZ2U7IHM8c3ViPmk8XC9zdWI+ICsgdzxzdWI+aTxcL3N1Yj4pPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFjMDBcdWFkNmNcdWI5N2MmbmJzcDtcdWM3OTFcdWM1YzVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWJhODVcdWM3NzRcdWIyZTQuIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViYTQ4XHVjZDk0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVhYzAwXHVhZDZjXHViOTdjJm5ic3A7XHVjNzkxXHVjNWM1XHVkNTU4XHViMjk0IFx1YWM4M1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YzdhMFx1YzJkYyBcdWJhNDhcdWNkOTggXHVjNzkxXHVjNWM1XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzc0XHVjNWI0XHVjMTFjIFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzQwIFx1Yzc3Y1x1Yzc0NCBcdWM4MTVcdWMyMTggXHVjMmRjXHVhYzA0XHVjNzdjIFx1YjU0YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAgXHViMDVkXHViMGI4XHViMmU0LiBcdWQzYjhcdWM3NThcdWMwYzEgXHVjMmRjXHVhYzA0XHVjNzQwIDEsIDIsIDMsIC4uLiwgbWF4e2Q8c3ViPmk8XC9zdWI+fVx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWFjMDBcdWFkNmNcdWI5N2MmbmJzcDtcdWI5YzhcdWFjMTAgXHVjMmRjXHVhYzA0IFx1YzgwNFx1YzVkMCBcdWM2NDRcdWMxMzFcdWQ1NThcdWIyOTQgXHViMmU0XHVjNzRjXHViMmVjIFx1YzBkZFx1YzBiMCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzZkMFx1Yzc1OCBcdWMyMTggbVx1YWNmYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWMwMFx1YWQ2Y1x1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbSAmbGU7IDEwLCAxICZsZTsgbiAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWFjMDBcdWFkNmNcdWM3NTggXHVjODE1XHViY2Y0IHM8c3ViPmk8XC9zdWI+LCB3PHN1Yj5pPFwvc3ViPiwgZDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbHQ7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgNTAwLCAxICZsZTsgdzxzdWI+aTxcL3N1Yj4gJmxlOyBkPHN1Yj5pPFwvc3ViPi1zPHN1Yj5pPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IG5cdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4IFx1YWMwMFx1YWQ2Y1x1Yzc1OCBcdWM4MWNcdWM3OTEgXHVjMmE0XHVjZjAwXHVjOTA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWQ2NDBcdWMyMThcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICZxdW90O2ssIGE8c3ViPjE8XC9zdWI+LCBiPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIGI8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPms8XC9zdWI+LCBiPHN1Yj5rPFwvc3ViPiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBrXHViMjk0IFx1YzJkY1x1YWMwNCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgKGE8c3ViPmo8XC9zdWI+LCBiPHN1Yj5qPFwvc3ViPilcdWIyOTQgYTxzdWI+ajxcL3N1Yj5cdWJkODBcdWQxMzAgYjxzdWI+ajxcL3N1Yj5cdWFlNGNcdWM5YzAgXHVkNTVjIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWFkZjggXHVhYzAwXHVhZDZjXHViOTdjJm5ic3A7XHVjODFjXHVjNzkxXHVkNTVjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gKGE8c3ViPmk8XC9zdWI+ICZsdDsgYjxzdWI+aTxcL3N1Yj4gJmx0OyBhPHN1Yj5pKzE8XC9zdWI+XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQpIFx1YjljY1x1YzU3ZCwgXHViYWE4XHViNGUwIFx1YWMwMFx1YWQ2Y1x1Yjk3YyBcdWM2NDRcdWMxMzFcdWQ1NThcdWIyOTQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzEzOFx1YzZiOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVybml0dXJlIEZhY3RvcnkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBtIHdvcmtlcnMgaW4gS2ltIHMgZnVybml0dXJlIGZhY3RvcnkuIEFsbCB3b3JrZXJzIGhhdmUgYW4gZXF1aXZhbGVudCBsZXZlbCBvZiBza2lsbCBhbmQgcHJvZHVjdGl2aXR5LiBUaGUgZmFjdG9yeSBoYXMgdGFrZW4gbiBvcmRlcnMgZm9yIG5leHQgbW9udGggcyB3b3JrLiBBIG1hbmFnZXIgb2YgdGhlIGZhY3RvcnkgbWFkZSBhIHByZWxpbWluYXJ5IHBsYW4gZm9yIGFsbCBvcmRlcnMgYXMgZm9sbG93czogRm9yIGFuIG9yZGVyIGksIHRoZSBlYXJsaWVzdCBzdGFydCB0aW1lIHM8c3ViPmk8XC9zdWI+IGlzIHRoZSBlYXJsaWVzdCB0aW1lIGF0IHdoaWNoIGEgd29ya2VyIGNhbiBzdGFydCB3b3JraW5nIG9uIHRoZSBvcmRlci4gVGhlIHdvcmtpbmcgdGltZSB3PHN1Yj5pPFwvc3ViPiBpcyB0aGUgdGltZSByZXF1aXJlZCB0byBjb21wbGV0ZSB0aGUgb3JkZXIuIFRoZSBkZWFkbGluZSBkPHN1Yj5pPFwvc3ViPiBpcyB0aGUgdGltZSBieSB3aGljaCB0aGUgb3JkZXIgbXVzdCBiZSBmaW5pc2hlZC4gQ2VydGFpbmx5LCBkPHN1Yj5pPFwvc3ViPiAmZ2U7IHM8c3ViPmk8XC9zdWI+ICsgdzxzdWI+aTxcL3N1Yj4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuIG9yZGVyIGlzIGRlYWx0IHdpdGggYnkgb25seSBvbmUgd29ya2VyIGF0IGFueSBtb21lbnQuIEl0IGlzIHBvc3NpYmxlIHRoYXQgYSB3b3JrZXIgc3RvcHMgaGlzIGN1cnJlbnQgd29yayBhbmQgd29ya3Mgb24gYW5vdGhlciBvcmRlci4gQSBzdXNwZW5kZWQgd29yayBjYW4gYmUgcmVzdW1lZCBieSBhbnkgd29ya2VyLiBBbGwgd29ya2VycyBiZWdpbiBhbmQgc3RvcCB0aGVpciB3b3JrIGF0IGludGVncmFsIHRpbWVzLiBTbywgdGltZSBpcyBudW1iZXJlZCAxLCAyLCAzLCAuLi4sIG1heHtkPHN1Yj5pPFwvc3ViPn0sIGZvciBzaW1wbGljaXR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UsIGEgbWFuYWdlciBvZiB0aGUgZmFjdG9yeSwgYXJlIGdvaW5nIHRvIG1ha2UgYSBkZXRhaWxlZCBzY2hlZHVsZSBmb3IgbmV4dCBtb250aCYjMzk7cyBwcm9kdWN0aW9uLiBHaXZlbiB0aGUgcHJlbGltaW5hcnkgcGxhbiBmb3IgdGhlIG4gb3JkZXIgcmVxdWVzdHMsIHdyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIGEgc2NoZWR1bGUgc3VjaCB0aGF0IGFsbCBvcmRlcnMgYXJlIGZpbmlzaGVkIGJ5IHRoZWlyIGRlYWRsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIG0gYW5kIG4gKDEgJmxlOyBtICZsZTsgMTAsIDEgJmxlOyBuICZsZTsgMTAwKSwgd2hlcmUgbSBpcyB0aGUgbnVtYmVyIG9mIHdvcmtlcnMgYW5kIG4gaXMgdGhlIG51bWJlciBvZiBvcmRlcnMuIEluIHRoZSBuZXh0IG4gbGluZXMgb2YgZWFjaCB0ZXN0IGNhc2UsIHRoZSBpLXRoIGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgczxzdWI+aTxcL3N1Yj4sIHc8c3ViPmk8XC9zdWI+LCBhbmQgZDxzdWI+aTxcL3N1Yj4gKGkgPSAxLCAyLCAuLi4gLCBuIGFuZCAxICZsZTsgczxzdWI+aTxcL3N1Yj4gJmx0OyBkPHN1Yj5pPFwvc3ViPiAmbGU7IDUwMCBhbmQgMSAmbGU7IHc8c3ViPmk8XC9zdWI+ICZsZTsgZDxzdWI+aTxcL3N1Yj4gLSBzPHN1Yj5pPFwvc3ViPiksIHdoaWNoIHJlcHJlc2VudCB0aGUgZWFybGllc3Qgc3RhcnQgdGltZSwgdGhlIHdvcmtpbmcgdGltZSwgYW5kIHRoZSBkZWFkbGluZSBmb3IgYW4gb3JkZXIgaSwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgaWYgdGhlcmUgaXMgbm8gc2NoZWR1bGUgc3VjaCB0aGF0IGFsbCBvcmRlcnMgYXJlIGZpbmlzaGVkIGJ5IHRoZWlyIGRlYWRsaW5lLCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgJnF1b3Q7MCZxdW90Oy4gT3RoZXJ3aXNlLCBwcmludCBuIGxpbmVzLiBUaGUgaS10aCBsaW5lIHNob3VsZCBjb250YWluIGFuIG9kZCBudW1iZXIgb2YgaW50ZWdlcnMgJnF1b3Q7aywgYTxzdWI+MTxcL3N1Yj4sIGI8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+azxcL3N1Yj4sIGI8c3ViPms8XC9zdWI+JnF1b3Q7IHdoaWNoIHJlcHJlc2VudCBhIHNjaGVkdWxlIGZvciB0aGUgaS10aCBvcmRlciwgaSA9IDEsIDIsIC4uLiwgbiwgd2hlcmUgayBtZWFucyB0aGUgbnVtYmVyIG9mIHRpbWUgaW50ZXJ2YWxzIGFuZCAoYTxzdWI+ajxcL3N1Yj4sIGI8c3ViPmo8XC9zdWI+KSBtZWFucyBhIHRpbWUgaW50ZXJ2YWwgdGhhdCBhIHdvcmtlciB3aWxsIGJlIHdvcmtpbmcgb24gaXQgZnJvbSBhPHN1Yj5qPFwvc3ViPiB0byBiPHN1Yj5qPFwvc3ViPi4gTm90aWNlIHRoYXQgYTxzdWI+aTxcL3N1Yj4gJmx0OyBiPHN1Yj5pPFwvc3ViPiAmbHQ7IGE8c3ViPmkrMTxcL3N1Yj4uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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