Internet Problem Solving Contest

• Easy input data set – A1
• Hard input data set – A2

You are in a casino, and you are anxious to play on the new one-armed bandit – a slot machine they just installed.

The slot machine has n wheels in a row. The i-th wheel from the left contains the integers from 1 to k_i, inclusive. When you pull the handle, the wheels will spin for a while. When they stop, each wheel will show you one of its integers. The integers are randomly chosen. All random choices are uniform and mutually independent.

Problem specification

You are given the number of wheels n and the size of every wheel k_i.

Easy subproblem A1: Output any sequence of numbers you could see on the given slot machine.

Hard subproblem A2: Suppose we ignore the spaces between the wheels and read the sequence of numbers as one long string of digits. Find the sequence of numbers that produces the lexicographically smallest such string.

Lexicographic order

When comparing two different strings S and T, find the smallest index i at which they differ. The one with a smaller character at that index is lexicographically smaller than the other. If there is no such character (i.e., one of the strings is a prefix of the other), the shorter string is the lexicographically smaller one.

For example:

• 22 is lexicographically smaller than 220 because 22 is a prefix of 220
• 123 is lexicographically smaller than 14 because 2 is less than 4.

Input specification

The first line of the input file contains an integer t ≤ 100 specifying the number of test cases. Each test case is preceded by a blank line.

Each test case begins with a line consisting of a single integers n. The following line contains n space-separated integers k₁, …, k_n. In both subproblems we have 1 ≤ n ≤ 1 000 and ∀i : 1 ≤ k_i ≤ 100.

Output specification

For each test case, output a single line with n integers separated by single spaces: the numbers as they appear on the individual wheels of the machine.

What to submit

Do not submit any programs. Your task is to produce and submit the correct output files a1.out and a2.out for the provided input files a1.in and a2.in.

Example for subproblem A1

Input:

2

3
6 6 6

2
10 2

Output for A1:

2 4 6
7 2

There are many other correct outputs. Any correct output will be accepted.

Example for subproblem A2

Input:

2

3
6 6 6

2
10 2

Output for A2:

1 1 1
10 1

The lexicographically smallest string consisting of 3 integers from 1 to 6 (inclusive) is 111.

The lexicographically smallest string consisting of an integer from 1 to 10 (inclusive) and an integer from 1 to 2 (inclusive) is 101. Note that this string is smaller than 11 because the second character in 101 is smaller than the second character in 11.