Sphere Online Judge

SPOJ Problem Set (classical)

8551. Colours A, B, C, D

Problem code: ABCD


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:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:originated from a mathematical problem

hide comments
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-03-03 18:52:32 californiagurl
getting SIGSEGV....anybody knows how to overcome that?
http://ideone.com/gno8bu
2014-02-12 11:21:05 Raghuvendra Singh


Last edit: 2014-02-12 17:31:19
2014-01-31 13:43:49 mad
@author...i am getting wa many times...can you plz check submission no. 10976986
2014-01-30 09:21:56 :)
no need of backtracking.
think in simple way :)
AC in 1st attempt
2014-01-05 15:47:33 Vipul Pandey
good one! normal bracktracking will give tle. think little differently.
2013-12-15 06:24:55 Mitch Schwartz
I believe a custom judge is being used that allows any correct solution to pass. My AC code prints a different result for the second example case. It could be checked more thoroughly, if someone were motivated to do so.

Last edit: 2013-12-15 06:32:08
2013-12-15 04:20:12 cegprakash
nowhere in the question it's mentioned lexicographical order. Why? All possible solutions will be accepted?
2013-10-31 17:56:18 Avaneesh Rastogi
Seems like a lot of people don't read the problem-statement carefully.
"There are exactly N cells of each colour (A, B, C and D) in the table."
Its clearly written.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.