Balanced Sotteok Skewer

Interview

Time limit1sMemory limit512 MB

Summary

Remove characters only from the left end of an s/t string to get the longest remaining suffix with equal counts of s and t.

Level: Easy3 of 10
Topics: String, Prefix sum
Solved: No attempts yet

Problem

A sotteok-sotteok is a long skewer with sausages and rice cakes threaded on it. For convenience, treat a sotteok-sotteok as a string of length $N$ made only of the letters s and t. The letter s stands for a sausage, and t stands for a rice cake. The figure above shows a sotteok-sotteok of length $7$ . Before eating, Eugene wants to turn it into a balanced sotteok-sotteok. A sotteok-sotteok is balanced when the number of sausages on the skewer equals the number of rice cakes on it. However, if no sausage and no rice cake are on the skewer, it is not balanced. The figure above has 3 sausages and 4 rice cakes, so it is not balanced. Eugene can remove the sausage or rice cake at the leftmost end. The right end is the handle, so removing from the right is impossible. The figure below shows the sausage at the leftmost end removed. Eugene then removes two more rice cakes. Now there are 2 sausages and 2 rice cakes, so the skewer is balanced. Given the sotteok-sotteok Eugene wants to eat, what balanced sotteok-sotteok of maximum length can be made through this process?

Input

The first line contains the length $N$ ( $2 \le N \le 100$ ) of the sotteok-sotteok. The second line contains a string of length $N$ that represents the sotteok-sotteok. The string consists only of the letters s and t. The input is never a case that cannot be turned into a balanced sotteok-sotteok through this process.

Output

Print the shape of the balanced sotteok-sotteok of maximum length that can be made through this process.

Examples3

Example 1
Input
```
7
sttstts
```
Expected output
```
stts
```
Example 2
Input
```
4
ttts
```
Expected output
```
ts
```
Example 3
Input
```
4
stst
```
Expected output
```
stst
```