[USACO08JAN] iCow B
题目描述
被无止境的农活压榨得筋疲力尽后,FarmerJohn 打算用他在 MP3 播放器市场新买的 iCow 来听些音乐,放松一下。FJ 的 iCow 里存了 $N(1 \le N \le 1{,}000)$ 首曲子,按 $1..N$ 依次编号。至于曲子播放的顺序,则是按一个 FarmerJohn 自己设计的算法来决定:
- 第 $i$ 首曲子有一个初始权值 $R_i\ (1 \le R_i \le 10{,}000)$。
- 当一首曲子播放完毕,接下来播放的将是所有曲子中权值最大的那首(如果有两首或多首曲子的权值相同,那么这些曲子中编号最小的那首会被选中)。
- 一首曲子在播放结束后,它的权值会被平均地分给其他 $N-1$ 首曲子,它本身的权值清零。
- 如果一首曲子的权值无法被平均分配(也就是说,无法被 $N-1$ 整除),那么被 $N-1$ 除的余数部分将会以 $1$ 为单位,顺次分配给排名靠前的曲子(也就是说,顺序为曲目 $1$ 、曲目 $2 \cdots $ 依次下去。当然,刚播放过的那首曲子需要被跳过),直到多出的部分被分配完。
在选定的下一首曲子播放完毕后,这个算法再次被执行,调整曲子的权值,并选出再接下来播放的曲目。
请你计算一下,按 FJ 的算法,最先播放的 $T\ (1 \le T \le 1000)$ 首曲子分别是哪些。
输入输出格式
输入格式
第 $1$ 行有两个用空格隔开的整数:$N$ 和 $T$。
第 $2$ 至第 $N+1$ 行,第 $i+1$ 行为 $1$ 个整数 $R_i$。
输出格式
输出共 $T$ 行,第 $i$ 行输出一个整数,表示 iCow 播放的第 $i$ 首曲子。
输入输出样例
输入样例 #1
3 4
10
8
11
输出样例 #1
3
1
2
3
说明
每一首曲子播放前,三首曲子的权值分别为:
- $[10,8,11]$。播放 $\#3$,$11/2 = 5$,权值余量为 $1$。
- $[16,13,0]$。播放 $\#1$,$16/2 = 8$。
- $[0,21,8]$。播放 $\#2$,$21/2 = 10$,权值余量为 $1$。
- $[11,0,18]$。播放 $\#3$,……