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:

\n\n

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

\n

It is guaranteed that the solution, not necessarily unique, will always exist.

\n\n

Input

\n

[a natural number N ≤ 50000]

\n

[a string of 2N letters from the set {A, B, C, D}, representing the first row of the table]

\n\n

Output

\n

[a string of 2N letters from the set {A, B, C, D}, representing the second row of the table]

\n\n

Example

\n

Input:\n1\nCB\n\nOutput:\nAD

\n\n

Input:\n2\nABAD\n\nOutput:\nBCDC

统计

递交统计

Colours A, B, C, D

信息

状态

开发

支持

还没有账户？

登录