장바구니의 예산 선택

문제

한 온라인 쇼핑몰은 장바구니에서 일부 항목을 골라 별도의 구매 목록으로 옮기는 기능을 만든다. 장바구니에는 N개의 항목이 있으며, 화면에 위에서부터 보이는 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 항목에는 가격 하나가 기록되어 있다. 같은 상품을 여러 번 담았더라도 장바구니의 각 항목은 독립적으로 취급하므로, 가격이 같다는 이유로 항목을 합치지 않는다. 사용자는 이번에 구매할 항목 수 K를 정한다. 쇼핑몰은 장바구니의 모든 항목을 가격이 낮은 순서로 비교하여 정확히 K개를 선택한다. 가격이 같은 항목끼리는 장바구니에서 더 위에 있는 항목, 즉 원래 번호가 작은 항목을 먼저 선택한다. 따라서 가격과 원래 번호를 차례로 비교하면 모든 항목의 선택 우선순위가 하나로 정해진다. 할인, 배송비, 상품 수량 등 가격 외의 조건은 고려하지 않는다. 선택이 끝난 뒤 구매 목록을 표시하는 순서는 선택 우선순위와 다르다. 구매 목록에서는 사용자가 원래 장바구니의 배치를 알아볼 수 있도록, 선택된 항목들의 원래 번호를 작은 순서대로 나열한다. 선택되지 않은 항목은 구매 목록에 나타나지 않으며, 번호를 새로 붙이지도 않는다. 예를 들어 뒤쪽에 있는 저렴한 항목을 먼저 선택했더라도, 함께 선택된 앞쪽 항목이 있다면 구매 목록에서는 앞쪽 항목의 번호를 먼저 표시한다. K는 항상 1 이상 N 이하이므로 구매 목록이 비는 경우는 없다. 모든 항목의 가격이 같다면 번호가 가장 작은 K개를 선택한다. 가격 목록과 K가 주어졌을 때 최종 구매 목록에 표시할 원래 번호들을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 1번부터 N번까지 항목의 가격 P_i가 공백으로 구분되어 주어진다. 각 가격은 정수이며 1 ≤ P_i ≤ 999이다.

출력

선택된 K개 항목의 원래 번호를 오름차순으로 한 줄에 출력한다. 번호 사이는 공백 하나로 구분한다.

6 3
90 40 40 20 70 40

2 3 4

5 2
18 18 18 18 18

1 2

4 4
8 3 9 2

1 2 3 4

출처: Devin.KR 자체 제작