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
2016-03-09 14:36:18 poojan
2 WA ans But Finally Got It Awsome Que! One wa bcs Not terminate string '\0':
Very Good Que! Must do!
2016-02-24 15:19:52 enigmus
Hint: Try building up your solution from smaller pieces
2016-02-18 17:23:42 Ankit
My program runs for a O(n) but still it gives Time Limit Exceeded. Stuck badly. !!
2016-02-17 13:13:54 Ankit
TLE after 18. The numbers in the bracket, any idea what it means ?
2016-01-15 12:53:12 minhthai
try to think super simply :)
2015-12-16 20:15:07
WA at 18th test case...can anyone help please..?
2015-10-18 11:00:37
read carefully statement 1 ..!!!!
2015-08-02 04:25:08 (Tjandra Satria Gunawan)(曾毅昆)
Finally AC, it's hard to think the solution but very easy to implement :)
2015-07-09 17:10:53 Shubhransh Srivastav
wa on running judge 18.... don't know why :(

Last edit: 2015-07-13 19:30:43
2015-06-04 07:37:37 Diksha Jaiswal
tle with backtracking :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.