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
2013-06-21 04:23:56 suman
Can anyone check my solution. I m getting right answer for every tricky case given in comments.. but still wrong answer
2013-06-20 16:58:57 akshay khanna
if we print the input array from 2nd element till the end i.e 2n-1 characters; and print the last character such that it is not equal to previous one, shouldn't it give the correct answer ?
like for input ABCBAD output would be BCBADA... last 2n-1 characters of input and first 2n-1 characters of output remain the same... but this approach gives WA... why ?

Last edit: 2013-06-20 17:01:23
2013-04-10 11:33:54 pranav gupta
will any solution do or it has to be smallest one in lexicographical order? Could you please provide me a test case where my solution is going wrong. I've tried too long to debug this now without knowing what exactly to debug.
2013-03-28 16:49:36 ahmed ashry
nice one !!
2013-03-27 14:20:23 Ouditchya Sinha
@Viktor Fonic My AC solution gives CDBDCB for your input :)
2013-03-17 11:52:49 dirty
WA at case 18. I dont know why .. Test Case is messy :(
2013-03-13 19:41:51 Viktor Fonic
Here's an interesting case:
3
ABACAD

Output:
BCDBDC
2013-03-11 14:36:03 Vitalis Salis
@Shubham Dude don't give the algorithm. Some may want to think about it themselves.

Last edit: 2013-03-11 14:36:15
2013-02-17 01:47:59 Curiosa
Pls check my solution, what's wrong with it. It seems that it works, but gives me WA. I've checked it on every provided cases.
2013-02-14 16:08:49 Shivam Agrawal
WA at test case 18...any1 please help

Last edit: 2013-02-14 16:11:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.