ABCD - Colours A, B, C, D

Consider a table with 2 rows and 2N columns (a total of 4N cells). Each cell of the first row is coloured by one of the colours A, B, C, D such that there are no two adjacent cells of the same colour. You have to colour the second row using colours A, B, C, D such that:

  • There are exactly N cells of each colour (A, B, C and D) in the table.
  • There are no two adjacent cells of the same colour. (Adjacent cells share a vertical or a horizontal side.)

It is guaranteed that the solution, not necessarily unique, will always exist.

Input

[a natural number N ≤ 50000]

[a string of 2N letters from the set {A, B, C, D}, representing the first row of the table]

Output

[a string of 2N letters from the set {A, B, C, D}, representing the second row of the table]

Example

Input:
1
CB

Output:
AD
Input:
2
ABAD

Output:
BCDC

Added by:Adrian Satja Kurdija
Date:2011-03-13
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:inspired by a math puzzle

hide comments
2017-12-21 19:53:32
Became one of my fav problem :) .Got one runtime error as max size of array will be 2*n I took n. Solved myself, made my day!!
Real test case are after 16....I think!
2017-07-24 23:50:31
stuck on test case 18....ques is very easy though i am wondering where am i making mistake
2017-04-11 12:41:30 candide
Accurate problem description. Solution needs much more tricky logic than algorithmics. Keep it simple! remember: you have 4 colors and each row has even length ...
2017-03-21 15:21:48 Pratik Ritesh
really nice problem..try breaking down to subproblem (keep in mind length of given row is even)..:)
2017-02-17 08:23:35
getting WA answer after 18th testcase any suggestions .
2017-01-30 21:10:37
what is meant by first condition ??
2016-12-16 18:16:04
Tried again after a long time...this time AC in second go after a stupid runtime error i made. Even after getting AC i couldn't believe it was so simple .. :p


Last edit: 2016-12-16 18:59:58
2016-06-02 08:58:42 sanjay
Took a long time to get AC
2016-05-20 16:34:58
If stuck at testcase 9.....try this..
3 ABACAD
answer can be :DCBDCB
was a life saver ...finally ac :-)
2016-05-08 04:52:11
Two compilation errors because I forgot to remove a few isolated references to a debugging macro I added, but after I did that I got and AC on my first scored submission (which at this point in my development as a programmer is quite an accomplishment!). Like usual, I spent all night coming up with a convoluted algorithm that included multi-dimensional arrays and random number generation, but eventually gave up and realized while I was out for the day how simple the solution for this actually is! Completely trashed my original approach and ended up finishing it in about 2 hours... like well-designed algorithms so often seem to be, the best approaches are often much simpler than they first appear. In any case, this site is great, I can see an immense improvement in my understanding of many concepts since I've been here. Cheers!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.