Under construction

Still being built. Things may change

iCow

Time limit1sMemory limit128 MB

Summary
Repeatedly pick the highest-rated song, reset its rating to 0, and spread its points over the others until T songs are played.
Level

Medium4 of 10

Topics
Simulation, Implementation, Greedy
Solved
No attempts yet

Problem

Weary from the endless toil of farming, Farmer John has decided to try the MP3 player market with his new iCow. The iCow stores NN songs (1≤N≤10001 \le N \le 1000), numbered 11 through NN, and plays them in a "shuffled" order determined by Farmer John's own algorithm:

  • Each song ii has an initial rating RiR_i (1≤Ri≤100001 \le R_i \le 10000).
  • The next song to be played is always the one with the highest rating. If two or more songs are tied, the one with the smallest index is chosen.
  • Once a song is played, its rating is set to 00, and the points it held are distributed evenly among the other N−1N-1 songs.
  • If the points cannot be distributed evenly (that is, they are not divisible by N−1N-1), the leftover points are handed out one at a time to the lowest-numbered songs first (R1R_1, R2R_2, and so on, but never the song that was just played) until no leftover points remain.
  • After the next song is played, this process repeats with the updated ratings.

Determine the first TT songs (1≤T≤10001 \le T \le 1000) that the iCow plays.

Input

  • Line 1: Two space-separated integers, NN and TT.
  • Lines 2 to N+1N+1: Line i+1i+1 contains a single integer RiR_i.

Output

  • Lines 1 to TT: Line ii contains the index of the ii-th song that the iCow plays.

Examples1

  1. Example 1

    Input
    3 4
    10
    8
    11
    
    Expected output
    3
    1
    2
    3