점프 게임

KOI 사가 출시한 점프 게임은 일렬로 늘어선 $N$개의 발판을 여러 번의 점프로 통과하는 게임이다. 수직선 위에 $N$개의 발판이 있고, 왼쪽에서 오른쪽으로 $0, 1, \dots, N-1$번 번호가 매겨져 있다. 처음에 주인공은 가장 왼쪽의 0번 발판에 있으며, 점수는 0점이다.

모든 $0 \le i \le N-1$에 대해, 주인공은 $i$번 발판에서 걷기 또는 점프 중 하나를 선택한다. 걷기를 고르면 $i+1$번 발판으로 이동하며 점수는 그대로다. 점프를 고르면 $i+K$번 발판으로 이동하며 점수가 $A[i]$만큼 증가한다. 여기서 $K$는 미리 정해진 수이다. 주인공이 $N-1$번 발판의 오른쪽으로 나아가면 게임이 성공적으로 끝난다. $N, N+1, \dots$번 발판은 실제로 존재하지 않지만, 이 번호에 도달하면 $N-1$번 발판의 오른쪽에 도달한 것으로 처리한다. 게임의 목표는 주인공을 적절히 조종해 점수를 최대로 만들고 게임을 끝내는 것이다.

KOI 사의 개발자들은 이 많은 발판을 일일이 설계할 수 없어서 단순한 방법으로 발판을 구성했다. 먼저 모든 $A[i]$를 0으로 설정한 뒤, $Q$번의 연산을 수행한다. 각 $j$($0 \le j \le Q-1$)에 대해 구간 $0 \le L[j] \le R[j] \le N-1$을 고르고, $A[L[j]], A[L[j]+1], \dots, A[R[j]]$를 각각 1씩 증가시킨다. 모든 연산을 마친 배열 $A$가 각 발판에서 점프했을 때 얻는 점수이다.

당신은 KOI 사의 점프 게임을 최대 점수로 끝내는 방법을 설명하는 컴퓨터 과학 영상을 만들고 있다. 발판은 $10^{12}$개에 이를 수 있으므로 효율적인 알고리즘이 필요하다.

• $1 \le N \le 10^{12}$
• $1 \le Q \le 250\,000$
• $1 \le K \le N$
• 모든 $0 \le j \le Q-1$에 대해 $0 \le L[j] \le R[j] \le N-1$