実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
英小文字および (
, )
からなる長さ N の文字列 S が与えられます。
以下の操作を可能な限り繰り返したあとの S を出力してください。
- S の連続部分文字列であって、最初の文字が
(
かつ 最後の文字が)
かつ 最初と最後以外に(
も)
も含まないものを自由に 1 つ選び削除する
なお、操作を可能な限り繰り返したあとの S は操作の手順によらず一意に定まることが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- N は整数である
- S は英小文字および
(
,)
からなる長さ N の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
8 a(b(d))c
出力例 1
ac
例えば、以下の手順により操作後の S が ac
となります。
- S の 4 文字目から 6 文字目までからなる部分文字列
(d)
を削除する。S はa(b)c
となる。 - S の 2 文字目から 4 文字目までからなる部分文字列
(b)
を削除する。S はac
となる。 - これ以上操作を行うことはできない。
入力例 2
5 a(b)(
出力例 2
a(
入力例 3
2 ()
出力例 3
操作後の S は空文字列になる可能性があります。
入力例 4
6 )))(((
出力例 4
)))(((
Score : 400 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters and the characters (
and )
.
Print the string S after performing the following operation as many times as possible.
- Choose and delete a contiguous substring of S that starts with
(
, ends with)
, and does not contain(
or)
other than the first and last characters.
It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.
Constraints
- 1 \leq N \leq 2 \times 10^5
- N is an integer.
- S is a string of length N consisting of lowercase English letters and the characters
(
and)
.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
8 a(b(d))c
Sample Output 1
ac
Here is one possible procedure, after which S will be ac
.
- Delete the substring
(d)
formed by the fourth to sixth characters of S, making ita(b)c
. - Delete the substring
(b)
formed by the second to fourth characters of S, making itac
. - The operation can no longer be performed.
Sample Input 2
5 a(b)(
Sample Output 2
a(
Sample Input 3
2 ()
Sample Output 3
The string S after the procedure may be empty.
Sample Input 4
6 )))(((
Sample Output 4
)))(((