괄호

(와 )로 이루어진 괄호 문자열이 올바른 괄호 문자열인지는 다음 규칙으로 정한다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. $X$가 올바른 괄호 문자열이면 $(X)$도 올바른 괄호 문자열이다.
3. $X$와 $Y$가 올바른 괄호 문자열이면 둘을 이어 붙인 $Z = XY$도 올바른 괄호 문자열이다.

예를 들어 (()), ()(), (()())()는 올바른 괄호 문자열이고, (와 ())는 올바른 괄호 문자열이 아니다.

길이가 $n$인 괄호 문자열이 주어진다. 이 문자열은 올바르지 않을 수도 있다. 구간 뒤집기를 최대 한 번 해서 올바른 괄호 문자열로 만들 수 있는지 판별하라. 구간 뒤집기는 1부터 세는 두 인덱스 $l$과 $r$ ($1 \le l \le r \le n$)을 골라 닫힌 구간 $[l, r]$에 속한 괄호를 모두 뒤집는 연산이다. 뒤집으면 여는 괄호 (는 닫는 괄호 )가 되고, 닫는 괄호 )는 여는 괄호 (가 된다.

())(는 구간 $[3, 4]$를 뒤집으면 올바른 괄호 문자열이 된다. ()))는 구간 $[3, 3]$을 뒤집어도 되고 구간 $[2, 2]$를 뒤집어도 된다. 반면 )))(는 어떤 구간을 뒤집어도 올바른 괄호 문자열이 되지 않는다.

첫 줄에 괄호 문자열이 주어진다. 길이는 1 이상 5000 이하이며, 문자열은 (와 )로만 이루어진다.

구간 뒤집기를 최대 한 번 해서 올바른 괄호 문자열로 만들 수 있으면 possible을, 만들 수 없으면 impossible을 출력한다.