Contest Duration: - (local time) (150 minutes) Back to Home
E - Synchronized Subsequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 個の aN 個の b からなる，長さ 2N の文字列 S が与えられます。

あなたは S からいくつかの文字を選びます。ただし各 i = 1,2,...,N について，Si 番目に出現する ai 番目に出現する b から片方だけ選ぶことは出来ません。 そして選んだ文字たちを( S での順番通りに)結合します。

こうして得られる文字列のうち，辞書順で最大のものを求めて下さい。

制約

• 1 \leq N \leq 3000
• SN 個の ab からなる，長さ 2N の文字列である。

N
S

3
aababb

出力例 1

abab

S1, 3, 4, 6 番目の文字からなる部分列 T は，条件を満たします。

3
bbabaa

bbabaa

6
bbbaabbabaaa

bbbabaaa

入力例 4

9
abbbaababaababbaba

出力例 4

bbaababababa

Score : 1600 points

Problem Statement

You are given a string S of length 2N, containing N occurrences of a and N occurrences of b.

You will choose some of the characters in S. Here, for each i = 1,2,...,N, it is not allowed to choose exactly one of the following two: the i-th occurrence of a and the i-th occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).

Find the lexicographically largest string that can be obtained in this way.

Constraints

• 1 \leq N \leq 3000
• S is a string of length 2N containing N occurrences of a and N occurrences of b.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the lexicographically largest string that satisfies the condition.

3
aababb

Sample Output 1

abab

A subsequence of T obtained from taking the first, third, fourth and sixth characters in S, satisfies the condition.

3
bbabaa

Sample Output 2

bbabaa

You can choose all the characters.

6
bbbaabbabaaa

bbbabaaa

Sample Input 4

9
abbbaababaababbaba

bbaababababa