가중 윈도우 합

길이가 n인 수열이 주어진다. 윈도우는 수열에서 연속된 부분 수열이다. 예를 들어 수열 $[3, 6, 2, 3, 5, 4]$에는 크기가 3인 윈도우가 $[3, 6, 2]$, $[6, 2, 3]$, $[2, 3, 5]$, $[3, 5, 4]$의 네 개 있다. 크기 k인 윈도우 i는 i번째 값에서 시작하여 연속된 k개의 값을 포함한다. 따라서 마지막 값은 (i+k-1)번째 값이다.

값이 $a_1, a_2, \ldots, a_k$인 윈도우의 가중 윈도우 합은 다음과 같이 정의한다.

$1a_1 + 2a_2 + 3a_3 + \cdots + ka_k$

위의 네 윈도우의 가중 윈도우 합은 다음과 같다.

• $[3, 6, 2]$는 $1 \times 3 + 2 \times 6 + 3 \times 2 = 21$ (순위 2)
• $[6, 2, 3]$은 $1 \times 6 + 2 \times 2 + 3 \times 3 = 19$ (순위 1)
• $[2, 3, 5]$는 $1 \times 2 + 2 \times 3 + 3 \times 5 = 23$ (순위 3)
• $[3, 5, 4]$는 $1 \times 3 + 2 \times 5 + 3 \times 4 = 25$ (순위 4)

주어진 크기의 윈도우를 가중 윈도우 합이 작은 순서로 정렬한다. 합이 같으면 시작 인덱스가 작은 윈도우를 먼저 놓는다.

정수 수열과 윈도우 크기가 주어졌을 때, 그 크기의 모든 윈도우를 가중 윈도우 합 기준으로 정렬하라.

첫 줄에 두 정수 n (1 ≤ n ≤ 2 × 10^5)과 k (1 ≤ k ≤ n)이 주어진다. 각각 수열의 길이와 윈도우의 크기이다. 다음 n개의 줄에는 수열의 값이 순서대로 한 줄에 하나씩 주어진다. 각 값은 1 이상 10^8 이하이다.

정렬된 윈도우 목록을 한 줄에 윈도우 하나씩 출력한다. 각 윈도우에 대해 시작 인덱스와 가중 윈도우 합을 차례로 출력한다.