공연장 안내지 배포 계획

문제

공연장 운영팀은 개장 전에 각 좌석에 안내지를 놓으려 한다. 이번 공연에는 여러 종류의 안내지가 있으며, 배포 담당자는 자신이 맡은 안내지를 연속된 좌석 구간에 같은 수량씩 놓는다. 운영팀이 확인하려는 것은 안내지의 종류가 아니라 각 좌석에 최종적으로 놓이는 안내지의 총 장수다. 좌석 번호는 왼쪽부터 1번부터 N번까지이며, 처음에는 모든 좌석에 안내지가 한 장도 없다. 배포 계획 하나는 세 정수 L, R, V로 표현한다. 이 계획은 L번 좌석부터 R번 좌석까지의 모든 좌석에 각각 안내지 V장을 추가한다는 뜻이다. 양 끝의 좌석도 배포 구간에 포함한다. 구간 밖의 좌석에는 이 계획으로 안내지를 놓지 않는다. L과 R이 같으면 좌석 하나에만 V장을 추가한다. 모든 계획은 한 번씩 실행하며, 안내지를 회수하거나 다른 좌석으로 옮기는 작업은 없다. 서로 다른 계획의 구간은 겹칠 수 있다. 겹치는 좌석에는 각 계획에서 정한 장수가 모두 더해진다. 내용이 완전히 같은 계획이 여러 번 주어져도 각각 별개의 배포 작업이므로 모두 적용한다. 예를 들어 어떤 좌석이 2장을 추가하는 계획과 3장을 추가하는 계획에 포함되면, 두 작업을 마친 뒤 그 좌석에는 이 두 계획으로 총 5장이 놓인다. 계획의 실행 순서는 최종 장수에 영향을 주지 않는다. 운영팀은 안내지가 지나치게 쌓이는 좌석을 미리 확인하려 한다. 모든 배포 계획을 적용했을 때 좌석별 총 장수의 최댓값, 그 최댓값을 갖는 좌석 중 번호가 가장 작은 좌석, 그리고 최댓값을 갖는 좌석의 개수를 구한다. 안내지가 놓이지 않은 좌석도 조사 대상에 포함한다. 배포 계획이 하나도 없다면 모든 좌석의 장수가 0이므로 최댓값은 0, 가장 작은 좌석 번호는 1, 해당 좌석의 개수는 N이 된다.

입력

첫째 줄에 좌석 수 N과 배포 계획 수 M이 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하인 정수이고 M은 0 이상 20,000 이하인 정수다. 다음 M개 줄에 계획을 나타내는 정수 L, R, V가 공백으로 구분되어 주어진다. 각 계획은 1 ≤ L ≤ R ≤ N과 1 ≤ V ≤ 9를 만족한다.

출력

좌석별 총 장수의 최댓값, 그 최댓값을 갖는 가장 작은 좌석 번호, 최댓값을 갖는 좌석의 개수를 이 순서대로 공백 하나로 구분하여 한 줄에 출력한다.

7 3
1 3 2
3 5 1
5 7 3

4 5 1

6 2
2 3 4
5 6 4

4 2 4

4 0

0 1 4

출처: Devin.KR 자체 제작