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.

Examples

Input

3
aababb


Output

abab


Input

3
bbabaa


Output

bbabaa


Input

6
bbbaabbabaaa


Output

bbbabaaa


Input

9
abbbaababaababbaba


Output

bbaababababa
#include<iostream>
#include<string>
using namespace std;

const int MAX = 6000;

string greedA(string S, int l) { // 先頭がaだった時の貪欲取得(abab…系)
	for (int i = 1, j, k;i < l;++ i) {
		if (S[i] == 'a') { // 連続した'a'を発見
			for (j = i + 1;S[j] == 'a';++ j); // 最初に出てくるb(消さない)
			for (k = j + 1;S[k] == 'a';++ k); // 次に出てくるb(消す)
			S.erase(S.begin() + k);
			S.erase(S.begin() + i);
			-- i;
		} else ++ i;
	}
	return S;
}

string greedB(string S, int l) { // 先頭がbだった時の探索(i決め打ち、i番目以降取る)
	string comp = S;
	for (int i = 0, ma = l >> 1, j;i < ma;i ++) {
		for (j = 1;comp[j] == comp[0];j ++);
		comp.erase(comp.begin() + j);
		comp.erase(comp.begin());
		S = S > comp ? S : comp;
	}
	return S;
}

int main() {
	int N;
	string S;
	cin >> N >> S;
	N = S.length();
	
	bool isA[MAX]; // isA[i] = S[i] == 'a'
	for (int i = 0;i < N;++ i) isA[i] = S[i] == 'a';
	
	int sum[MAX]; // 累積和、sum[i]は[0, i)までに出てきた'b'の数-出てきた'a'の数
	sum[0] = isA[0] ? -1 : 1;
	for (int i = 1;i < N;++ i) sum[i] = sum[i - 1] + (isA[i] ? -1 : 1);
	
	static string greed[MAX];
	int use = 0;
	
	string subst;
	for (int l = 0, r = 0;l < N;l = r, ++ r) {
		while(sum[r] != 0) ++ r; // ここまでで区間[l, r)の累積和は0、よって独立に解ける
		++ r;
		subst = S.substr(l, r - l);
		if (isA[l]) greed[use] = greedA(subst, r - l);
		else greed[use] = greedB(subst, r - l);
		use ++;
	}
	
	string ret = "";
	for (int i = use - 1;i >= 0;i --) { // 後は貪欲に構成
		ret = greed[i] + ret > ret ? greed[i] + ret : ret;
	}
	cout << ret;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

解説ACなので何も無いです、解説読んでね
*/