ABCD - Colours A, B, C, D

no tags 

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.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): 2015-03-28 00:56:52

There are several solutions, but if you apply the correct logic you will get one and only one.
Nice problem indeed.

chamini2: 2015-02-13 23:46:34

It's not test 18, it's wrong answer in general.

Malinga: 2014-12-25 16:23:20

Getting wrong answer in 18th test case...any suggestions please ??

Anubhav Balodhi : 2014-12-18 14:10:04

got AC, after lot of tries :-)

Retaliation: 2014-12-07 07:40:41

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
californiagurl: 2014-07-19 11:22:20

once you figure how it can be done in O(n), it just isn't a trouble anymore.
AC in first O(n) attempt . though dfs seems like the more natural solution,, it sure gives TLE

Francis: 2014-05-14 07:22:42

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
Rishav Goyal: 2014-03-11 11:42:21

weo ! nice indeed!

Kushagra Sinha: 2014-03-05 18:51:10

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 ...

newbie: 2014-01-31 13:43:49

@author...i am getting wa many times...can you plz check submission no. 10976986