연속 급수대 점검 구간

문제

마라톤 대회 운영팀은 코스를 따라 설치한 N개의 급수대에 물을 준비하고 있다. 급수대에는 출발점에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 급수대에 처음 준비된 물의 양은 정수 단위로 기록되어 있으며, 물이 전혀 없는 급수대도 있을 수 있다. 대회 시작 전에는 M건의 추가 보급이 이루어진다. 한 번의 보급 기록은 세 정수 L, R, V로 표현한다. 이는 번호가 L 이상 R 이하인 모든 급수대에 물을 각각 V만큼 추가한다는 뜻이다. L번과 R번 급수대도 보급 대상에 포함된다. 여러 보급의 대상 구간이 겹치면 해당 급수대에는 각 보급의 물이 모두 더해진다. 보급 과정에서 물이 소비되거나 다른 급수대로 옮겨지는 일은 없다. 모든 추가 보급이 끝난 뒤 운영팀은 이동 점검 차량이 방문할 구간을 하나 고르려고 한다. 차량은 연속한 K개의 급수대를 방문해야 한다. 시작 급수대가 s번이면 방문하는 급수대는 s번부터 s+K-1번까지이며, 코스의 끝을 넘어가거나 마지막 급수대에서 첫 급수대로 이어서 방문할 수는 없다. 운영팀은 방문하는 K개 급수대에 준비된 물의 총량이 가장 큰 구간을 선택한다. 총량이 가장 큰 구간이 여러 개라면 시작 급수대의 번호가 가장 작은 구간을 선택한다. 물의 양이 모두 0이어도 같은 기준을 적용한다. 초기 물의 양과 모든 추가 보급 기록을 바탕으로 선택할 구간의 시작 번호와 그 구간의 물 총량을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 20,000이고 0 ≤ M ≤ 20,000이다.
둘째 줄에 각 급수대에 처음 준비된 물의 양을 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 9이다.
다음 M개 줄에 추가 보급 기록을 나타내는 정수 L, R, V가 공백으로 구분되어 주어진다. 1 ≤ L ≤ R ≤ N이고 1 ≤ V ≤ 99이다.

출력

선택한 구간의 시작 급수대 번호와 그 구간에 준비된 물의 총량을 공백으로 구분하여 한 줄에 출력한다. 총량이 같은 구간이 여러 개이면 가장 작은 시작 번호를 출력한다.

5 2 2
1 0 2 1 0
2 4 3
4 5 2

3 11

4 0 2
3 1 3 1

1 4

3 1 3
0 0 0
1 3 2

1 6

출처: Devin.KR 자체 제작