Brackets

A bracket sequence made of ( and ) is valid exactly when the following rules build it.

1. The empty sequence is valid.
2. If $X$ is a valid bracket sequence, then $(X)$ is a valid bracket sequence.
3. If $X$ and $Y$ are valid bracket sequences, then their concatenation $Z = XY$ is a valid bracket sequence.

For example, (()), ()(), and (()())() are valid bracket sequences, while ( and ()) are not.

You are given a bracket sequence of length $n$. It might not be valid. Decide whether at most one segment inversion makes it a valid bracket sequence. A segment inversion picks two 1-based indices $l$ and $r$ ($1 \le l \le r \le n$) and inverts every bracket at an index in the closed interval $[l, r]$. After the inversion, a left bracket ( becomes a right bracket ), and a right bracket ) becomes a left bracket (.

Inverting the segment $[3, 4]$ makes ())( valid. Inverting the segment $[3, 3]$ makes ())) valid, and inverting the segment $[2, 2]$ does the same. No segment inversion makes )))( valid.

One line holds the bracket sequence. Its length is between 1 and 5000, and it contains only ( and ).

Print possible if at most one segment inversion makes the bracket sequence valid, and impossible otherwise.