ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1745. Ещё Один Ответ

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
После того, как Ещё Один Гигантский Суперкомпьютер работал в течение π миллионов лет, ёжики смогли узнать Ещё Один Ответ. На этот раз полученный Ответ оказался весьма загадочным. Даже для ёжиков, которые не знали, каким, собственно, был Вопрос.
Ответ состоял из n слов. Каждое слово — это непустая последовательность левых и правых скобок. Большинство ёжиков расстроились, увидев Ответ, но Пушистик был счастлив, ведь Пушистик просто обожал скобки. Но больше всего ему нравились правильные скобочные последовательности.
Правильная скобочная последовательность — это последовательность скобок, удовле­тво­ря­ющая следующим условиям:
  • Количество левых и правых скобок в последовательности совпадает;
  • Количество правых скобок в любом префиксе последовательности не превосходит количество левых.
  • Пушистик уверен, что ёжики просто обязаны узнать, как выглядит самая длинная скобочная последовательность, которую можно получить приписыванием друг к другу слов из Ответа по следующим правилам:
  • Каждое слово можно использовать не более одного раза;
  • Слова можно приписывать друг к другу в любом порядке.
  • Суперкомпьютер сейчас занят тем, что разрабатывает своего ещё более мощного наследника, поэтому Пушистик обратился за помощью в решении этой задачи к вам.

    Исходные данные

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

    Результат

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

    Примеры

    исходные данныерезультат
    4
    (
    (((
    (
    ))
    
    4 3
    1 3 4
    
    3
    ()
    (()
    )
    
    6 3
    2 3 1
    
    Автор задачи: Дамир Ахметзянов
    Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009