In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 23rd
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]

[AED028] Round-Robin

Suppose you have a queue of processes to be executed by a processor using a scheduling algorithm with a round-robin strategy:

1. Take the first process in the queue and execute it for a maximum of T seconds;
2. If the process is not yet finished, it goes to the end of the queue with T fewer seconds remaining;
3. Return to the first step, continuing to process the first process in the queue until all processes are completed.

Imagine, for example, that T=5 and the queue initially looks like this, where each number indicates the remaining time. The processor will go through 7 iterations before finishing:

Current time: 0 seconds (0 processor iterations)

emacs 9

firefox 3

bash 12

dia 5

The processor first executes emacs for 5 seconds. There are still 4 seconds remaining, and this process is now placed at the end of the queue:

Current time: 5 seconds (1 processor iteration)

firefox 3

bash 12

dia 5

emacs 4

As firefox needs less than 5 seconds, it runs for the 3 seconds it needs and finishes. The algorithm continues until all processes are completed:

Current time: 8 seconds (2 processor iterations) [firefox completes]

bash 12

dia 5

emacs 4

Current time: 13 seconds (3 processor iterations)

dia 5

emacs 4

bash 7

Current time: 18 seconds (4 processor iterations) [dia completes]

emacs 4

bash 7

Current time: 22 seconds (5 processor iterations) [emacs completes]

bash 7

Current time: 27 seconds (6 processor iterations)

bash 2

Current time: 29 seconds (7 processor iterations) [bash completes]
Queue empty

The Problem

Your task is to write a method to simulate this process, printing a line each time a process finishes with the name of the process, the time it finishes and how many processor iterations it took.

Input

The first line contains an integer T, the maximum execution time per iteration.

The second line contains an integer N, the number of processes in the queue. The next N lines contain processes in the format P_i R_i, where P_i is the name of the process and R_i the time it requires. The name consists only of lowercase letters, and the time is an integer.

Output

The output should contain N lines, describing the processes in the order they completed in the format PROCESS_NAME a b, where a is the time when the process finished, and b is the number of processor iterations when it happened.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

5
4
emacs 9
firefox 3
bash 12
dia 5

firefox 8 2
dia 18 4
emacs 22 5
bash 29 7