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

hide comments
Khoi Tran: 2013-01-30 02:36:14

Can anyone take a look at my solution? Why does it exceed time limit?
It's O(n) and I tried my best to optimize everything. Is it just a Python limitation?

ginnipkj: 2013-01-14 21:12:50

Sometimes u need to be greedy....:)

Shubham Somani: 2013-01-11 11:48:09

simple DFS! :P

Akhil Rao: 2013-01-09 06:21:22

for testcase
3
DBADBA
I am getting
CACBCD
Is it right??

Dhruv Goel: 2013-01-03 21:34:03

There was no extra line needed between n and input string for AC (in my case).

Anuj_LuckFove!: 2012-12-21 19:25:33

nice ques :) finally AC..no need to think too much for this..simplistic approach will work..

triveni: 2012-12-18 03:21:54

Thanks beginner, '\n' caused me also many wrong answers.. finally AC.. :(

Paul Draper: 2012-12-12 05:31:52

@Romal Thoppilan, some might think "TRickY but straightforward !" doesn't make much sense.

Retaliation: 2012-12-11 19:25:41

I am getting wrong ans on 18th test case. aren't every possible solutions covered for that test case ?

abdelkarim: 2012-09-14 12:55:02

i spend month to solve it and got AC
after 19 WA


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