Description

In a factory, there are n pairs of jobs, (p_i , q_i ), i = 1, 2, . . . , n, to be scheduled. Each job, p_i or q_i , needs 1 unit of time to process. All the jobs p_i , i = 1, 2, . . . , n, must be scheduled before of all the jobs q_i , i = 1, 2, . . . , n. The order among the jobs p_i , i = 1, 2, . . . , n, as well as the order among the jobs q_i , i = 1, 2, . . . , n, is not important. However, it is required that the time between p_i and q_i , measured from the starting time of p_i to the starting time of q_i , should be at most d_i , for i = 1, 2, . . . , n.

Given a sequence of n positive integers d₁ , d₂ , . . . , d_n , we want to know whether these n pairs of jobs can be scheduled in the time interval [0, 2n] or not. We say that the problem is solvable if the n pairs of jobs can be scheduled in a time interval of length 2n units, in such a way that the time between p_i and q_i is at most d_i , for i = 1, 2, . . . , n.

For example, for n = 3, the sequence 1, 3, 5 is solvable, since we can schedule these 3 pairs of jobs as follows:

The sequence 3, 3, 4, 6 is also solvable, since we can schedule the jobs in the following way:

In this problem, you are going to design a computer program to schedule pairs of jobs with the above constraints.

Technical Specification

Assume that n < 16, and each d_i < 2³¹ . For simplicity, assume that d₁ ≤ d₂ ≤ · · · ≤ d_n , Σ_i=1~k d_i ≥ k² for 1 ≤ k < n, and Σ_i=1~n d_i=n². Note that, in this case, if the problem is solvable then the time between each pair of jobs (p_i , q_i ) is exactly d_i . If the solution is not unique, try to schedule the jobs so that the job q_i with smaller index is finished as early as possible. For example, let the input requirements be 3 3 4 6. Then print out the solution p4 p1 p2 p3 q1 q2 q4 q3.

Input

Input file contains a set of test cases. Each test case contains a positive integer n, followed by n integers d_i, 1 ≤ i ≤ n. The last test case is followed by a line containing only one integer 0.

Output

Print the the job in ascending order of their starting time. Print one line for each test case and for readability print a space before each “p” and “q”. If the pairs of jobs cannot be scheduled, then print the message “no solution” in that line.

Sample Input  Download

Sample Output  Download

Tags

Discuss