После того, как Ещё Один Гигантский Суперкомпьютер работал в течение π миллионов лет, ёжики смогли узнать Ещё Один Ответ. На этот раз полученный Ответ оказался весьма загадочным. Даже для ёжиков, которые не знали, каким, собственно, был Вопрос.

Ответ состоял из n слов. Каждое слово — это непустая последовательность левых и правых скобок. Большинство ёжиков расстроились, увидев Ответ, но Пушистик был счастлив, ведь Пушистик просто обожал скобки. Но больше всего ему нравились правильные скобочные последовательности.

Правильная скобочная последовательность — это последовательность скобок, удовле­тво­ря­ющая следующим условиям:

Количество левых и правых скобок в последовательности совпадает;

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

Пушистик уверен, что ёжики просто обязаны узнать, как выглядит самая длинная скобочная последовательность, которую можно получить приписыванием друг к другу слов из Ответа по следующим правилам:

Каждое слово можно использовать не более одного раза;

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

Суперкомпьютер сейчас занят тем, что разрабатывает своего ещё более мощного наследника, поэтому Пушистик обратился за помощью в решении этой задачи к вам.

В первой строке записано количество слов в Ответе n (1 ≤ n ≤ 1000). В каждой из следующих n строк записано одно из этих слов. Суммарная длина слов не превосходит 10000.

В первой строке выведите через пробел числа l и k, где l — максимальная длина правильной скобочной последовательности, а k — количество слов, из которых она состоит. Во второй строке через пробел выведите k номеров использованных слов в том порядке, в котором их следует выписывать. Слова занумерованы числами от 1 до n в том порядке, в котором они даны на входе. Если возможных ответов несколько, выведите любой.