Обратите внимание на нестандартное ограничение по памяти.
Недавно Артур с Сашей изучили правильные скобочные последовательности. Артур отлично понял эту тему и ему настолько ею проникся, что завёл себе любимую правильную скобочную последовательность длины 2n. В отличие от Артура, Саша очень плохо понял тему про правильные скобочные последовательности, и назло Артуру сломал его любимую правильную скобочную последовательность.
Все, что помнит Артур о своей любимой последовательности — это для каждой открывающейся скобки '(' примерное расстояние до соответствующей ей закрывающейся ')'. Для i-й открывающейся скобки он помнит отрезок [li, ri], в котором лежит расстояние до соответствующей ей закрывающейся.
Формально говоря, для i-й открывающейся скобки (при их нумерации слева направо) известно, что разность позиций соответствующей ей закрывающейся скобки и её собственной позиции лежит в отрезке [li, ri].
Помогите Артуру восстановить его любимую правильную скобочную последовательность!
Выходные данные
Если по описанным данным возможно восстановить правильную скобочную последовательность, выведите любой возможный вариант.
Если же Артур что-то напутал, и последовательностей, соответствующих данной информации нет, выведите единственную строку «IMPOSSIBLE» (без кавычек).