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
2012-08-30 23:20:57 akb
Beautiful...:D
2012-08-20 07:37:39 vishal chaudhary
what's wrong with the 18th case??
2012-08-01 20:05:58 Naman
Lovely problem!!
2012-07-26 13:50:45 beginner :(
see that there is an extra '\n' between 'n' and the input string, that's why it was producing WA for many people,( atleast for me it was) , take care of that u will get AC

Last edit: 2012-07-26 13:54:26
2012-07-18 20:20:00 DivineAtheist
One if the good problems...finally got accepted after so many trails......:)
2012-07-13 05:53:54 saurabh kushwaha
plz anyone check my code. it's giving wa. my ques. id is 7307909.
2012-07-12 06:51:34 kumar rishabh
I am getting wrong answer in the question any test case plz?
2012-05-26 13:08:36 :p
getting WA on test case 18......some1 help plzz....
@Dinesh and @amit....are both of you able to upload it successfully?????

Last edit: 2012-05-26 13:10:20
2012-05-24 22:44:06 Dinesh
Getting WA on test case 18 ??? How..i tried all possible combo .
2012-05-07 10:09:46 Daman Bharat Garg
@Adrian: When I run my code on PC I achieve output for n~=50000 in 0.008 sec approx., so why am I getting TLE here?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.