MOZSATLA - Sharmeen and the Lost Array

Sharmeen loves array very much. Many days ago she wrote an array (of n elements and the index of this array is 1 based) in her notebook, but unfortunately she lost the notebook. She want to restore the array. The only clue she know that is if in any position(i) of the array (1<= i < n), the element in this position is greater than, equal or less than the next position(i+1) element.

Can you help her to restore the array?

Input

In the first line given an integer t (1 <= t <= 100), which is the number of test cases.

For each test case,

In the first line there will be given a positive integer n (1 <= n <= 105) which is the size of the lost array. In the next line there will be n - 1 integers Xi (0 <= Xi <= 2).

If, Xi = 0, then ith  element is equal to (i+1)th element of the lost array.

If, Xi = 1, then ith  element is less than (i+1)th element of the lost array.

If, Xi = 2, then ith  element is greater than (i+1)th element of the lost array.

Output

For each test case you have to output the lost array in one line. If multiple solution exist then you have to print the lexicographically smallest one. Elements of the lost array must be greater than zero.

For better understanding see the sample input output.

Example

Input:
1
5
1 2 0 1
Output: 1 2 1 1 2

Added by:Mozahid
Date:2019-04-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2024-08-06 19:33:15
I have run my code with standard test cases and the answers were correct but upon submission the answer shows wrong. Is it some internal issue or what? whom should i contact?
[Simes]: What do you mean by the standard test cases? How can you be certain your code gives the correct answer in all circumstances?

Last edit: 2024-08-07 18:12:25
2024-08-03 18:47:08
weird question

Last edit: 2024-08-03 18:47:30
2024-04-15 11:53:34
i dont even understand the question, lol
2024-03-22 08:23:14
Bullshit question!
2022-07-17 20:03:04
can anyone send the testcases? or where do i find the solution?
my standard testcase is running correct but on submission it shows wrong answer.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.