JUNL - BHAAD MEI JAAO

You are on vacation on a drunken island, but you couldn't resist the temptation of solving a good old problem. It all started when a group of kids played a game they call "The Falling Coconuts". In this game, a number of coconuts fall to the ground, one by one, on a single axis, at the locations given in drops. If a coconut X lands on the ground, it remains where it is. If it lands on top of another coconut Y, one of the following things happens:

If coconut Y is surrounded on both sides by coconuts (denoted by 'O'), coconut X remains where it is.

     X
    OYO

If there is no coconut directly to the right of coconut Y, coconut X slides down to the position directly to the right of coconut Y.

     X
    OY   ->  OYX
     X
     Y   ->   YX

If there is a coconut directly to the right of coconut Y, but no coconut directly to the left of coconut Y, coconut X slides down to the position directly to the left of coconut Y.

    X
    YO  ->  XYO

Each time coconut X slides down to a different position, it will continue to slide (following the behavior outlined above) until it's in a place where it will not slide any further.

The task is to display the final coconut configuration.

Input

First line is t = number of test cases.

Each test case consists of 2 lines, first line conataining the number of coconuts and second line contains n integers denoting the position of each coconut on the x-axis.

Output

As described in the problem statement.

Example

Input:
2
8
8 9 10 11 12 8 12 10
10
6 8 10 7 9 8 8 8 8 8

Output:
---O---
OOOOOOO
--O---
-OOO--
OOOOOO

Explanation of test case 1:

The configuration after each fallen coconut is given below:

X  ->  OX  ->  OOX  ->  000X  ->  0000X  ->  X00000  ->  000000X  ->  0000000

In this diagram, 'X' denotes the last fallen coconut.


Added by:Aradhya
Date:2012-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AVIRAL,YASH,AMAN,ARADHYA

hide comments
2012-10-16 15:51:43 Nitin Khanna
Can someone please explain the output sequence of second testcase?
2012-10-16 10:59:36 :D
Yes, on top of what Jared had written, print an empty line after each test case. I don't know if exact judge is used though, so maybe white space do not matter.

Also CounterinsurgectoR:
Correct the output description, don't just throw the text on SPOJ!
2012-10-15 09:00:47 theycallhimavi
Very well put jared.. :)
2012-10-14 17:35:41 Jared Deckard
Initial position: 0 ≤ Pi ≤ 18
Resting position: 0 ≤ Ri ≤ 26

Output:
Do not print any columns before the first coconut or after the last coconut.
Do not print any rows above the highest coconut.
Print 'O' if any position contains a coconut.
Print '-' if any position is empty.

Last edit: 2012-10-14 17:37:01
2012-10-14 06:06:40 Pranay
do we need to print '-' too ?
2012-10-13 14:02:58 Alex Anderson
The output description is strange and is compounded by the blank lines. Remove the blank lines between the first two outputs, and remove the lines between the final 3 outputs, and it will make more sense.
2012-10-13 10:37:39 Naman
You can assume n<100
2012-10-12 19:33:53 Snehasish Roy ;)
Output description is not clear :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.