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:  20110313 
Time limit:  0.190s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: SCM chicken 
Resource:  originated from a mathematical problem 
hide comments
Rajat (1307086):
20150328 00:56:52
There are several solutions, but if you apply the correct logic you will get one and only one.


chamini2:
20150213 23:46:34
It's not test 18, it's wrong answer in general. 

Malinga:
20141225 16:23:20
Getting wrong answer in 18th test case...any suggestions please ?? 

Anubhav Balodhi :
20141218 14:10:04
got AC, after lot of tries :) 

Retaliation:
20141207 07:40:41
I got an internal error while submitting the code in python.


californiagurl:
20140719 11:22:20
once you figure how it can be done in O(n), it just isn't a trouble anymore.


Francis:
20140514 07:22:42
after WA,TLE,SIGSEGV finally get AC in a simple way in O(n), but still TLE with backtrace and dfs.


Rishav Goyal:
20140311 11:42:21
weo ! nice indeed! 

Kushagra Sinha:
20140305 18:51:10
Finally AC ... not "simple" by any means ... it is an NPcomplete problem ... do not waste time trying to find a "simple" closedform solution ... 

newbie:
20140131 13:43:49
@author...i am getting wa many times...can you plz check submission no. 10976986 