서가 점검표의 가장 바쁜 칸

문제

도서관에는 왼쪽부터 1번부터 N번까지 번호가 붙은 서가 칸이 있다. 사서는 하루 동안 진행할 서가 점검 계획을 하나의 표로 정리하려고 한다. 각 계획은 연속한 여러 칸을 담당하며, 그 구간의 모든 칸에 같은 수의 점검 표시를 추가한다. 처음에는 어느 칸에도 점검 표시가 없다. 하나의 계획은 세 정수 L, R, W로 표현한다. 이 계획을 반영하면 L번 칸부터 R번 칸까지 양 끝을 포함한 모든 칸의 표시 수가 각각 W만큼 증가한다. 표시 수는 실제 책의 수가 아니라 사서가 확인해야 할 작업량을 나타내는 수치다. 따라서 같은 칸을 담당하는 계획이 여러 개라면 그 계획들이 추가한 표시를 모두 더한다. 서로 겹치는 계획도 그대로 적용하며, 같은 구간과 같은 표시 수를 가진 계획이 반복해서 주어져도 각각 별개의 계획으로 처리한다. 사서는 모든 계획을 반영한 뒤 표시 수가 가장 많은 칸에 안내판을 놓으려고 한다. 가장 많은 표시 수를 가진 칸이 여러 개라면 번호가 가장 작은 칸을 선택한다. 이때 선택한 칸의 번호와 그 칸의 최종 표시 수를 구해야 한다. 계획의 입력 순서는 최종 결과에 영향을 주지 않는다. 점검 계획이 하나도 없는 날도 있다. 이 경우에도 서가 칸은 적어도 하나 존재하며, 모든 칸의 표시 수를 0으로 취급하여 같은 선택 규칙을 적용한다. 어떤 계획에도 포함되지 않은 칸 역시 표시 수가 0이다. 계획에 적힌 구간을 줄이거나 표시를 다른 칸으로 옮기는 일은 허용하지 않는다. 주어진 모든 계획을 정확하게 반영한 결과를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ Q ≤ 20,000이다.
다음 Q개 줄에는 각 계획을 나타내는 정수 L, R, W가 공백으로 주어진다. 1 ≤ L ≤ R ≤ N, 1 ≤ W ≤ 1,000이다.

출력

선택한 칸의 번호와 그 칸의 최종 표시 수를 공백으로 구분하여 한 줄에 출력한다. Q가 0이면 1 0을 출력한다.

7 3
2 5 3
4 7 2
1 2 2

2 5

4 0

1 0

1 2
1 1 7
1 1 4

1 11

출처: Devin.KR 자체 제작