Задача #bav0003

Задача продублирована во вложении pdf

Михаил общается со своей очень хорошей подругой. Их общение длится

n

дней, каждый из которых можно представить в виде последовательности из открывающих и закрывающих круглых скобок. Их общение находится на грани разрыва, а поэтому вы (так как вы с ним похожи на братьев) должны спасти его.

Общение Михаила будет спасено в том и только в том случае, если возможно сконкатенировать эти

n

последовательностей в произвольном порядке так, чтобы в итоге получилась правильная скобочная последовательность. Это связано с тем, что тогда Михаил сможет доказать своей подруге, что он всегда пишет первым, да и к тому же столько же, сколько и она. Если не существует такого порядка конкатенации, то вы должны сообщить эту грустную новость Михалу, чтобы он подготовился к длительным грустным дням.

Напомним, что правильными скобочными последовательностями называются следующие последовательности скобок:

(),

(

A

), если

A

является правильной скобочной последовательностью,

A

B

, если

A

и

B

являются правильными скобочными последовательностями.

Формат входных данных

Первая строка содержит одно целое число

n

(

1

≤

n

≤

10

6

) — количество последовательностей.

Каждая из следующих

n

строк содержит непустую строку, состоящую из открывающих и закрывающих круглых скобок. Строки пронумерованы целыми числами от

1

до

n

в порядке следования. Заметьте, что эти строки не обязаны являться правильными скобочными последовательностями.

Гарантируется, что суммарная длина всех строк не превосходит

10

7

символов.

Формат выходных данных

Если спасти общение Михаила возможно, то выведите перестановку чисел от

1

до

n

— в каком порядке надо конкатенировать скобочные последовательности, чтобы в итоге получить правильную скобочную последовательность.

Если же Михаил обречен (то есть не существует требуемого порядка), то выведите число «-1» (без кавычек).