B. Дужкова інверсія | Rex IT Fest Div. 2

  1. REX IT FEST
  2. Rex IT Fest Div. 2
  3. B

Дужкова інверсія

Limits: 2 sec., 512 MiB

Якщо ми не можемо знайти рішення, це не означає, що його не існує.

Ендрю Вайлс

Петрик успішно впорався з минулим завданням, але через те, що ледве встиг вчасно здати його, одразу ж отримав нове - створити програму, яка перевіряє коректність послідовності дужок, а ще, окрім цього, пропонує способи вирішення проблеми, якщо послідовність не є коректною.

Послідовність дужок вважаємо коректною, якщо вона відповідає наступним умовам:

  1. Пуста послідовність завжди коректна.

  2. Якщо S - коректна послідовність, то (S) - теж коректна послідовність.

  3. Якщо S та T - коректні послідовності, то і їх конкатенація ST - теж коректна послідовність. Наприклад, конкатенація () та (()) - це ()(()).

Таким чином, (), (()) та ()() - коректні послідовності, а (,((), )))( - ні.

Ідея Петрика щодо способу вирішення вищеописаної проблеми полягає в наступному (назвемо це інверсією): програма обирає індекси \(l\) та \(r\) \((1 \leq l \leq r \leq n)\), де \(n\) - довжина послідовності дужок, та намагається замінити кожну з дужок на цьому інтервалі на протилежну - ( на ) та навпаки.

Нехай Петрик і придумав ідею, але не придумав реалізацію перевірки на те, чи можливо це зробити на даній послідовності дужок, і просить вас це зробити за нього.

Блоки тестів

  • Блок 1: 3 бали, \(1 \leq n \leq 3\).

  • Блок 2: 9 балів, рядок складається виключно з дужок одного типу (тобто лише ( або )).

  • Блок 3: 48 балів, \(1 \leq n \leq 100\).

  • Блок 4: 40 балів, без додаткових обмежень.

Input

У першому рядку задано рядок \(s\) — послідовність дужок ( та ) довжини \(n\).

Output

В єдиному рядку виведіть possible, якщо існує така інверсія заданої послідовності, що після неї послідовність стане коректною, інакше виведіть impossible.

Constraints

\(1 \leq n \leq 5000\)

Samples

Input (stdin) Output (stdout)
())) possible
Input (stdin) Output (stdout)
)((( impossible

Notes

У першому прикладі маємо ми можемо взяти \(l = 3\), \(r = 3\), застосувати на цьому відрізку інверсію і з ())) отримаємо ()(), що є коректною послідовністю дужок.

У другому прикладі не існує жодного способу застосувати інверсію таким чином, щоб ця послідовність дужок стала коректною.

Element TypeCreatedWhoProblemCompilerResultTime (sec.)Memory (MiB)#Actions