수족관 관람 통로의 조명

문제

한 수족관의 관람 통로에는 수조 N개가 일렬로 놓여 있다. 입구에서 가까운 순서대로 수조에 1부터 N까지 번호를 붙였다. 각 수조에는 현재 조명의 밝기를 나타내는 정수가 정해져 있다. 수족관은 새로운 야간 관람 행사를 준비하면서 여러 차례 조명 보강 작업을 진행한다. 각 작업은 연속한 수조들을 대상으로 하며, 지정된 구간의 모든 수조 밝기를 같은 양만큼 높인다. 조명 보강 작업 하나는 왼쪽 수조 번호 L, 오른쪽 수조 번호 R, 증가량 D로 주어진다. 이 작업을 수행하면 번호가 L 이상 R 이하인 모든 수조의 밝기에 D를 더한다. 양 끝 수조도 작업 대상에 포함한다. 같은 수조가 여러 작업의 대상이면 해당하는 모든 증가량을 더한다. 증가량이 0인 작업도 주어질 수 있으며, 그런 작업은 밝기를 바꾸지 않는다. 작업 중 밝기를 낮추거나 다른 값으로 덮어쓰는 일은 없다. 모든 작업이 끝나면 직원은 연속한 수조 K개를 골라 행사 안내 사진을 촬영한다. 사진에 포함된 수조들의 최종 밝기 합이 클수록 촬영에 적합하다고 판단한다. 선택한 첫 수조 번호가 X라면 사진에는 X번부터 X+K-1번까지의 수조가 포함된다. 통로의 끝과 처음은 이어져 있지 않으므로 번호 N을 넘어가는 선택은 허용하지 않는다. 직원은 밝기 합이 가장 큰 구간을 선택하려 한다. 같은 최대 합을 갖는 구간이 여러 개라면 첫 수조 번호가 가장 작은 구간을 선택한다. K는 1 이상 N 이하이므로 선택할 수 있는 구간은 항상 존재한다. 조명 보강 작업을 모두 반영한 뒤 선택한 구간의 첫 수조 번호와 최종 밝기 합을 구해야 한다. 처음의 밝기나 작업 도중의 밝기 합으로 구간을 선택해서는 안 된다.

입력

첫째 줄에 수조 수 N, 조명 보강 작업 수 M, 선택할 수조 수 K가 공백으로 주어진다. 모두 정수이며 1≤N≤20,000, 0≤M≤10,000, 1≤K≤N이다.
둘째 줄에 각 수조의 처음 밝기 A_1, A_2, …, A_N이 공백으로 주어진다. 각 밝기는 0 이상 1,000 이하의 정수이다.
다음 M개 줄에 작업을 나타내는 정수 L, R, D가 공백으로 주어진다. 1≤L≤R≤N, 0≤D≤1,000이다.

출력

선택한 구간의 첫 수조 번호와 해당 구간의 최종 밝기 합을 공백으로 구분하여 정수로 출력한다. 최대 합이 같은 구간이 여러 개라면 첫 수조 번호가 가장 작은 구간을 출력한다.

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

3 9

4 1 2
0 0 0 0
1 4 3

1 6

3 0 3
4 1 5

1 10

출처: Devin.KR 자체 제작