题目描述

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

条件を満たす $T$ のうち，辞書順で最大のものを出力して下さい。

题目大意

有一个长度为 $2 N$ 的仅由字符 $\mathtt{a}, \mathtt{b}$ 构成的字符串，且 $\mathtt{a}$ 的个数恰好等于 $\mathtt{b}$ 的个数，都出现了 $N$ 次。

你需要保留一些字符，剩下的字符删掉。对于一个 $i$，你可以保留从左往右数的第 $i$ 个 $\mathtt{a}$ 和第 $i$ 个 $\mathtt{b}$。

注意，对于这两个字符，只能同时保留或同时删掉，不能只保留其中一个。

请你求出能得到的字典序最大的串。

• $1 \le N \le 3 \times {10}^3$。

3
aababb

abab

3
bbabaa

bbabaa

6
bbbaabbabaaa

bbbabaaa

9
abbbaababaababbaba

bbaababababa

提示

制約

• $1\ \leq\ N\ \leq\ 3000$
• $S$ は $N$ 個の a と b からなる，長さ $2N$ の文字列である。

Sample Explanation 1

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

Sample Explanation 2

全ての文字を選ぶことも可能です。