01204212/job queue

from 01204212

Job queue 1

You have n jobs to be executed in k servers, called server 0, server 1,..., and server k-1 (1 <= n <= 100,000; 1 <= k <= 100). These n jobs are job 0, job 1, job 2,..., job n-1. Each job i has to be processed by server s[i].

All jobs arrive to our system in order from job 0 to job n-1, and when it arrives it goes to the server that will process it. Each server processes jobs in the order that they arrive to the server. We assume that before the system starts processing any jobs, all jobs arrive at our system and are assigned to appropriate server queues.

The system works in synchronous rounds. Every server takes 1 unit of time to process any job. Although every server should finish working at the same time, we assume that server 0 finishes slightly faster server 1, server 1 finishes slightly faster than server 2, and so on. In this way we can distinguish the time that each job finished its processing. Finally, after each server finishes processing the current job, it takes next job in the queue to process for the next round.

Your task is to output the sequence of jobs that have been processed ordered by the time servers finish processing them.

Consider the following example where n=5, k=3, and the values of s are as follows:

i    s[i]
---------
0     0
1     2
2     0
3     1
4     2

After all tasks arrived, the queues at the servers are like these:

servers       job queues
-----------------------------------
0             0, 2
1             3
2             1, 4

After the first round where jobs 0, 3, 1 have been processed (in this order), the queues are like these:

servers       job queues
-----------------------------------
0             2
1             
2             4

In this 2nd round, jobs 2 and 4 have been processed (in this order), and there are no more jobs left.

The list of finished jobs (in the required order) is

0, 3, 1, 2, 4

Input/output

Input

First line: integers n and k Next n lines: each line 2+i, for 0 <= i < n, contains integer s[i], where 0 <= s[i] < k

Output There are n lines of output specifying jobs number in order that they have been processed.

Example

Input

5 3
0
2
0
1
2

Output

0
3
1
2
4

Job queue 2

In this task, each job's requirement gets more complex. Each job can specified a list of servers that it has to goes through (in order) to get everything done.

You have n jobs to be executed in k servers, called server 0, server 1,..., and server k-1 (1 <= n <= 100,000; 1 <= k <= 100). These n jobs are job 0, job 1, job 2,..., job n-1. Each job i has to be processed by m[i] servers, specified by s[i][0], s[i][1], ..., s[i][m[i]-1].

All jobs arrive to our system in order from job 0 to job n-1, and when it arrives it goes to the server that will process it. Each server processes jobs in the order that they arrive to the server. We assume that before the system starts processing any jobs, all jobs arrive at our system and are assigned to appropriate server queues.

The system works in synchronous rounds. Every server takes 1 unit of time to process any job. Although every server should finish working at the same time, we assume that server 0 finishes slightly faster server 1, server 1 finishes slightly faster than server 2, and so on. In this way we can distinguish the time that each job finished its processing. Finally, after each server finishes processing the current job, it takes next job in the queue to process for the next round.

Your task is to output the sequence of jobs that have been processed ordered by the time servers finish processing them.

Consider the following example where n=5, k=3, and the values of s are as follows:

i    s[i]
---------
0     0
1     2
2     0
3     1
4     2

After all tasks arrived, the queues at the servers are like these:

servers       job queues
-----------------------------------
0             0, 2
1             3
2             1, 4

After the first round where jobs 0, 3, 1 have been processed (in this order), the queues are like these:

servers       job queues
-----------------------------------
0             2
1             
2             4

In this 2nd round, jobs 2 and 4 have been processed (in this order), and there are no more jobs left.

The list of finished jobs (in the required order) is

0, 3, 1, 2, 4

Input/output

Input

First line: integers n and k Next n lines: each line 2+i, for 0 <= i < n, contains integer s[i], where 0 <= s[i] < k

Output There are n lines of output specifying jobs number in order that they have been processed.

Example

Input

5 3
0
2
0
1
2

Output

0
3
1
2
4