As operator of the communications centre, your job is to direct messages intercepted from the enemy to the decryption centre as to gather intelligence. Given the critical nature of the messages, your goal is to direct each encrypted message to the decryption centre with the shortest waiting time.
You will be given ~N~ messages each containing ~C~ alphanumeric characters. Assuming that it takes ~C~ seconds to decrypt each message, output a list of the centres to direct the messages to in the order that they were given as to minimize the time it will take to decrypt all of them.
There are ~M~ centres numbered from ~1~ to ~M~. In the case of multiple suitable centres, choose the one with the smallest number.
The first line of input will contain ~N~, ~(1 \le N \le 100)~ the number of messages.
The next ~N~ lines of input will each contain a message of length ~C~, ~(1 \le C \le 100)~.
The last line of input will contain ~M~, ~(1 \le M \le 20)~ the number of centres at your disposal.
The output should consist of ~N~ lines, each containing the centre every message will be directed to, in the order they were given.
3 We Love DMOPC 2
1 2 1
Explanation for Sample Input
Centres 1 and 2 both start off with a waiting time of zero, but 1 is chosen as it comes before 2. The waiting time for 1 is now 2 seconds. For the second message centre 2 is chosen as its queue is empty. The third message is directed to centre 1 as it has a shorter waiting time (2<4).
Note that all messages must be decrypted – the enemy might be trying to mislead the operator by encrypting it such that it appears as another message.