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-01-26 01:48:06 Xx100m
Same Problem! Getting WA in test case 18.
I think their output file does not contain all the possible solutions (permutations) for the test case 18. The author of the problem needs to review his output file.
2012-01-07 19:06:59 Neeraj Pradhan
Same problem! WHY do i get WA in test case 18..?
2012-01-03 19:29:32 Abhishek Mishra
i m getting WA in case 18 plz explain.?PLZ EXPLAIN ASAP WHERE MY PROGRAM FAILS?

Last edit: 2012-01-03 21:18:00
2011-12-26 13:37:02 Aerofoil Kite
WHY do i get WA in test case 18..?
2011-09-27 11:14:12 Sotirios Nikoloutsopoulos
@Adrian Satja Kurdija

at testcase
3
DBADBA

My output is
CABCDC

is this wrong? if so why?
2011-09-14 09:34:58 Adrian Satja Kurdija
@Sotirios: your code fails on the following test case:

3
ADCADC
2011-09-14 09:34:58 Adrian Satja Kurdija
@Pranit: your code fails on the following test case:

3
DBADBA
2011-09-14 09:34:58 Romal Thoppilan
...... TRickY but straightforward !
2011-09-14 09:34:58 Adrian Satja Kurdija
Your solution prints debug information, like "Scanning to fill space"

Last edit: 2011-05-22 11:56:32
2011-09-14 09:34:58 Ravi Kiran
Nice problem! :-)
Beware: Take care of initialisation of maximum length to 2*MAXN and not MAXN. (Took me 3 SIGABRT's to realise it.)

Last edit: 2011-04-27 09:12:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.