기적의 신약

조는 생물의학 연구자다. 그는 무서운 병의 치료제를 거의 완성했다. 신약을 만들려면 값이 비싸고 일정 시간이 지나면 성질을 잃는 특수 효소가 있어야 한다. 지금은 임상시험 단계라서 매 시각 같은 양의 약을 준비해야 하고, 약 한 번 분량에는 효소가 하나 들어간다.

앞으로 $n$시간의 가격이 주어진다. 시각 $i$에는 가격 $c_i$로 효소를 원하는 만큼 살 수 있다. 효소의 수명은 $h$시간이라서 시각 $i$에 산 효소는 시각 $i$부터 시각 $i + h - 1$까지 쓸 수 있다. 시각 $1$부터 시각 $n$까지 매 시각 효소를 하나씩 쓸 때, 전체 구매 비용이 가장 적은 계획을 구하라.

가격이 같으면 조는 효소를 미리 쌓아 두지 않고 더 신선한 효소를 산다. 그래서 구매 계획은 다음 규칙으로 하나만 정해진다. 시각 $i$에 쓸 효소는 구간 $[\max(1,\ i - h + 1),\ i]$ 안에서 가격이 가장 싼 시각에 산다. 가장 싼 시각이 여럿이면 그중 가장 늦은 시각을 고른다.

입력은 데이터 집합 여러 개로 이루어지고 파일 끝에서 끝난다. 각 데이터 집합은 시간의 수 $n$, 효소의 수명 $h$, 출력 구간의 시작 시각 $b$와 끝 시각 $e$, 그리고 가격 $c_1, c_2, \dots, c_n$을 이 순서로 담는다. 수와 수 사이에는 공백과 줄바꿈이 자유롭게 올 수 있다.

• $1 \le n < 10000$
• $1 \le h < 10000$
• $1 \le b \le e \le n$
• $0 \le c_i < 10000$

데이터 집합마다 한 줄씩, 조가 시각 $b$부터 시각 $e$까지 각 시각에 사는 효소의 개수를 탭 문자로 구분해 줄 맨 앞부터 출력한다.