Task 3. Queue Jumpers

Available Marks: 10

The residents of Q-Town love queuing for the theatre. Some of them also consider particular position numbers to be lucky, so there can be a lot of undignified jostling while waiting in line. The Mayor of Q-Town wants to put a stop to this unseemly behaviour. She decrees that all theatregoers must adhere to the following rules:

• People initially form a queue in the order they arrive at the theatre.
• Just before the theatre opens, everyone in decreasing age order is allowed to nominate a position in the queue they would like to occupy.
• Nobody can nominate a position that has already been nominated, so all nominations are distinct, and
• Nominations are optional.

On the mayor's signal, everyone re-orders themselves in a dignified way. Those who did not nominate a position are shuffled up or down the queue as needed, maintaining their relative order.

Your task

Write a program to manage Q-Town's orderly queuing system. Input consists of one queuing problem per line, preceded by the number of problems. Each queuing problem consists of the number of patrons, to a maximum of 26, and the position each one would like to occupy. Positions are counted from 1, and 0 means no nomination.

People are allocated an upper-case letter in the original queue order, and the solution is the new arrangement of letters representing the revised queue. Assume the data is valid. The program should show both the original order and the final order on separate lines, with a space between each letter.

Example

3
3 0 0 0
9 9 8 7 6 5 4 3 2 1
5 0 1 5 0 2

A B C
A B C

A B C D E F G H I
I H G F E D C B A

A B C D E
B E A D C

Test data

Test your program using the following data.

5
4 4 2 3 1
6 0 0 5 3 4 1
13 0 0 1 2 3 4 5 6 7 8 9 10 11
26 12 13 3 0 15 0 9 10 8 0 0 14 0 2 4 5 0 7 0 11 1 0 0 0 6 0
1 0

Assessment

• 2 marks per problem.

You may submit multiple times. Only your most recent submission for each question will be marked.

Image: Microsoft Corp. clipart