COCI 2008/2009, Contest #4

Task MJEHURIC

Goran has five wooden pieces arranged in a sequence. There is a number between 1 and 5 inscribed on
every piece, so that every number appears on exactly one of the five pieces.

Goran wants to order the pieces to form the sequence 1, 2, 3, 4, 5 and does it like this:
  1. If the number on the first piece is greater than the number on the second piece, swap them.
  2. If the number on the second piece is greater than the number on the third piece, swap them.
  3. If the number on the third piece is greater than the number on the fourth piece, swap them.
  4. If the number on the fourth piece is greater than the number on the fifth piece, swap them.
  5. If the pieces don't form the sequence 1, 2, 3, 4, 5, go to step 1.
Write a program that, given the initial ordering of the pieces, outputs the ordering after each swap.

Input

The first line contains five integers separated by single spaces, the ordering of the pieces.
The numbers will be between 1 and 5 (inclusive) and there will be no duplicates.
The initial ordering will not be 1, 2, 3, 4, 5.

Output

After any two pieces are swapped, output the ordering of the pieces, on a single line separated by spaces.

Examples

Input

2 1 5 3 4

Output

1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

Input

2 3 4 5 1

Output

2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

All Submissions
Best Solutions


Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

why is my code getting WA???

You're skipping a few steps.
Try outputting your sequence after every iteration.

Man I had to solve a+b to help you
hardest problem of my life

still dont get it

I print my sequence after each swap...

your output doesnt even work on the sample cases

works on repl.it and ideone.com

unless they're both wrong


Since you might have to do the steps over and over again, you should use a loop. Since you do the steps until the pieces are in order, you should use a repeat loop. As for steps 1 to 4, just follow the instructions.

that is how i code it

Two things:
1. If you want help because you're getting the answer wrong, say so. Otherwise it looks like you want help because you don't know how to solve the problem. Why can't you take an extra few seconds to be specific?
2. You seem to assume that only one of each of the steps 1-4 can be done each cycle. As a matter of fact, this is not true --- always go through these steps in order, and re-print the sequence after each swap, but do not go back to step 1 after performing a swap. Only go back to step 1 after you reach step 5.

thx and i am sorry pls forgive me

I can't believe there's a bubble sort problem =D