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
2015-05-27 12:31:32 CoNtRaDiCtIoN
awesome problem :)
2015-03-28 00:56:52 Rajat (1307086)
There are several solutions, but if you apply the correct logic you will get one and only one.
Nice problem indeed.
2015-02-13 23:46:34 chamini2
It's not test 18, it's wrong answer in general.
2014-12-25 16:23:20 Malinga
Getting wrong answer in 18th test case...any suggestions please ??
2014-12-18 14:10:04 Anubhav Balodhi
got AC, after lot of tries :-)
2014-12-07 07:40:41 Retaliation
I got an internal error while submitting the code in python.
id is 13082356

[reply by cyclops: Python 3.4 is not available on Pyramid cluster, but as all problems are being migrated to Cube this will soon be a non-issue.]

Last edit: 2014-12-07 16:56:26
2014-05-14 07:22:42 Francis
after WA,TLE,SIGSEGV finally get AC in a simple way in O(n), but still TLE with backtrace and dfs.
hints:
(1)input format is:
1
CB
rather than:
1

CB
(2)test cases found in the forum and below
3
ABACAD
2
ABAD
3
DBADBA
3
ACBACB
3
ADCADC
7
ABCDABDADBDABD


Last edit: 2014-05-14 07:23:12
2014-03-11 11:42:21 Rishav Goyal
weo ! nice indeed!
2014-03-05 18:51:10 Kushagra Sinha
Finally AC ... not "simple" by any means ... it is an NP-complete problem ... do not waste time trying to find a "simple" closed-form solution ...
2014-01-31 13:43:49 newbie
@author...i am getting wa many times...can you plz check submission no. 10976986
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.