Brackets

Interview

Time limit2sMemory limit512 MB

Summary

Given a bracket string, decide whether flipping the brackets in at most one contiguous segment can turn the whole string into a balanced, valid bracket sequence.

Level: Medium6 of 10
Topics: Greedy, Prefix sum, String, Implementation
Solved: No attempts yet

Problem

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

The empty sequence is valid.
If $X$ is a valid bracket sequence, then $(X)$ is a valid bracket sequence.
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.

Input

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

Output

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

Examples3

Example 1
Input
```
()))
```
Expected output
```
possible
```
Example 2
Input
```
)))(
```
Expected output
```
impossible
```
Example 3
Input
```
()
```
Expected output
```
possible
```