ABX

$N$개의 A와 $N$개의 B로 이루어진 문자열 $T$에서 A가 놓인 위치를 $a_1,a_2,\cdots ,a_N$, B가 놓인 위치를 $b_1,b_2,\cdots ,b_N$이라고 하자. 문자열 $T$의 점수 $f(T)$는 같은 문자끼리의 거리의 총합으로 정의되며, $f(T) =\sum_{i=1}^{N}\sum_{j=1}^{N}(|a_i-a_j|+|b_i-b_j|)$으로 계산한다.

A, B, X로 구성된 길이가 $2N$인 문자열 $S$가 주어진다. $S$에는 A와 B가 각각 최대 $N$개 포함되어 있다. 여러분은 X를 A 또는 B로 적절히 바꿔서, A와 B의 개수가 각각 정확히 $N$이 되도록 만들어야 한다.

점수를 최소화하는 문자열과 최대화하는 문자열을 구하라.

첫째 줄에 $N$이 주어진다.

둘째 줄에 $S$가 주어진다.

$N$개의 A와 $N$개의 B로 이루어진 문자열 2개를 한 줄에 하나씩 출력한다.

첫째 줄에 점수를 최소화하는 문자열, 둘째 줄에 점수를 최대화하는 문자열을 출력한다. 이러한 문자열이 여러 개 존재할 경우, 그중 아무거나 출력한다.

• 주어지는 모든 수는 정수이다.
• $1\le N\le 3\, 000$
• $S$는 A, B, X로 이루어진 길이가 $2N$인 문자열로, A와 B는 각각 최대 $N$번 등장한다.