E$.$ A$2$: Deepest Substring

time limit per test$1$ second

memory limit per test$256$ megabytes

inputstandard input

outputstandard output

The deepest substring of a string containing text in nested parenthesis is the substring which is enclosed in the maximum number of parenthesis. For example, the deepest substring of a$+(($b$+$c$)+$d$)$ is b$+$c$.$

Your program should take as input a string containing nested parenthesis and print out its deepest substring. If there is more than one substring at the deepest level then your program should output the first one. For example, on input a$+(($b$+$c$)+($d$+$e$))$ your program should output b$+$c$.$

You can assume the input string will contain at most $1000$ characters that are only letters or parentheses $($i$.$e$.,$ no spaces$)$ and contains balanced parentheses $($every open parenthesis has a corresponding closing parenthesis$).$ You should read the input via standard input and print out nothing except the deepest substring followed by a newline.

Note. Your implementation must run in

O$($n$)$

operations where

n

is the length of the input string.