IOI '01 - Tampere, Finland
A Finnish high technology company has a big rectangular depot. The depot
has a worker and a manager. The sides of the depot, in the order around
it, are called left, top, right and bottom. The depot area is divided
into equal-sized squares by dividing the area into rows and columns. The
rows are numbered starting from the top with integers
The depot has containers, which are used to store invaluable technological devices. The containers have distinct identification numbers. Each container occupies one square. The depot is so big, that the number of containers ever to arrive is smaller than the number of rows and smaller than the number of columns. The containers are not removed from the depot, but sometimes a new container arrives. The entry to the depot is at the top left corner.
The worker has arranged the containers around the top left corner of the depot in such a way that he will be able to find them by their identification numbers. He uses the following method.
Suppose that the identification number of the next container to be
inserted is
1 4 5
2 9
3
The manager comes to the worker and they have the following dialogue:
Manager: Did container
Worker: No, that is impossible.
Manager: Oh, so you can tell the arrival order of the containers by
their placement.
Worker: Generally not. For instance, the containers now in the depot
could have arrived in the order
As the manager does not want to show that the worker seems much smarter, he goes away. You are to help the manager and write a program which, given a container placement, computes all possible orders in which they might have arrived.
Input Specification
The first line contains one integer
Output Specification
The output should contain as many lines as there are possible arrival
orders. Each of these lines contains
Sample Input 1
3
3 1 4 5
2 2 9
1 3
Sample Output 1
3 2 1 4 9 5
3 2 1 9 4 5
3 4 2 1 9 5
3 2 4 1 9 5
3 2 9 1 4 5
3 9 2 1 4 5
3 4 2 9 1 5
3 4 9 2 1 5
3 2 4 9 1 5
3 2 9 4 1 5
3 9 2 4 1 5
3 4 2 9 5 1
3 4 9 2 5 1
3 2 4 9 5 1
3 2 9 4 5 1
3 9 2 4 5 1
Sample Input 2
2
2 1 2
1 3
Sample Output 2
3 1 2
1 3 2
Scoring
If the output file contains impossible orders or no orders at all, your
score is
Comments