Во время раскопок в одной из пещер были обнаружены старинные надписи. Каждая из найденных записей представляла собой некоторое число N и правильную скобочную последовательность (ПСП).

Напомним, что ПСП может быть определена так:

• пустая строка является ПСП;
• если S является ПСП, то (S) также является ПСП;
• если S₁ и S₂ являются ПСП, то S₁S₂ является ПСП.

По некоторым из записей археологи поняли, что первое число обозначает количество подстрок в ПСП, которые также являются ПСП. Это навело археологов на мысль, что если они восстановят оставшиеся надписи, то им будет доступно какое-то тайное знание. Поскольку на стенах пещеры в основном обнаружены числа, то они считают, что восстановление отсутствующих ПСП возможно. Также ученые узнали, что длина каждой из ПСП не должна превышать 10⁵ символов, поскольку может не поместиться на стену в пещере.

Соответственно, теперь им необходимо построить такую ПСП, которая содержит в себе ровно N подстрок, которые также являются ПСП.