Codeforces Global Round 17 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

greedy

hashing

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. AmShZ Wins a Bet

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRight before the UEFA Euro 2020, AmShZ and Safar placed bets on who'd be the champion, AmShZ betting on Italy, and Safar betting on France.

Of course, AmShZ won. Hence, Safar gave him a bracket sequence $$$S$$$. Note that a bracket sequence is a string made of '(' and ')' characters.

AmShZ can perform the following operation any number of times:

- First, he cuts his string $$$S$$$ into three (possibly empty) contiguous substrings $$$A, B$$$ and $$$C$$$. Then, he glues them back by using a '(' and a ')' characters, resulting in a new string $$$S$$$ = $$$A$$$ + "(" + $$$B$$$ + ")" + $$$C$$$.
For example, if $$$S$$$ = "))((" and AmShZ cuts it into $$$A$$$ = "", $$$B$$$ = "))", and $$$C$$$ = "((", He will obtain $$$S$$$ = "()))((" as a new string.

After performing some (possibly none) operations, AmShZ gives his string to Keshi and asks him to find the initial string. Of course, Keshi might be able to come up with more than one possible initial string. Keshi is interested in finding the lexicographically smallest possible initial string.

Your task is to help Keshi in achieving his goal.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input

The only line of input contains a single string $$$S$$$ — the string after the operations $$$(1\le |S|\le 3 \cdot 10^5)$$$.

It is guaranteed that the first character of $$$S$$$ is ')'.

Output

Print the lexicographically smallest possible initial string before operations.

Example

Input

)(()(())))

Output

)((())))

Note

In the first sample, you can transform ")((())))" into ")(()(())))" by splitting it into ")(", empty string, and "(())))". It can be shown that this is the lexicographically smallest possible initial string

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 08:43:23 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|