Обратите внимание на нестандартное ограничение по памяти.

Недавно Артур с Сашей изучили правильные скобочные последовательности. Артур отлично понял эту тему и ему настолько ею проникся, что завёл себе любимую правильную скобочную последовательность длины 2n. В отличие от Артура, Саша очень плохо понял тему про правильные скобочные последовательности, и назло Артуру сломал его любимую правильную скобочную последовательность.

Все, что помнит Артур о своей любимой последовательности — это для каждой открывающейся скобки '(' примерное расстояние до соответствующей ей закрывающейся ')'. Для i-й открывающейся скобки он помнит отрезок [l_i, r_i], в котором лежит расстояние до соответствующей ей закрывающейся.

Формально говоря, для i-й открывающейся скобки (при их нумерации слева направо) известно, что разность позиций соответствующей ей закрывающейся скобки и её собственной позиции лежит в отрезке [l_i, r_i].

Помогите Артуру восстановить его любимую правильную скобочную последовательность!