ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Yet Another Answer

Time limit: 1.0 second
Memory limit: 64 MB
Eventually, after running Yet Another Stupendous Supercomputer for π million of years, hedgehogs happen to know Yet Another Answer. This time the Answer they got was quite surprising. Even for hedgehogs who didn't actually know what the Question was.
In fact, the Answer consists of n words. Each word is a nonempty sequence of left and right brackets. Whilst most of the hedgehogs were rather frustrated with the Answer, Fluffy was happy, because Fluffy likes brackets so much. But most of all he likes regular bracket sequences.
A regular bracket sequence is a sequence of brackets which satisfies the following conditions:
  • The sequence contains an equal number of left and right brackets;
  • The number of right brackets in any prefix of the sequence doesn't exceed the number of left ones.
  • Fluffy is sure that it's vitally important for the hedgehogs to know what is the longest regular bracket sequence one can make by concatenating the words of the Answer under the following rules:
  • Each word can be used at most once;
  • Words can be used in the arbitrary order.
  • Because the Supercomputer is so busy designing its yet more powerful successor, Fluffy hopes you can help him to solve the problem.

    Input

    The first line contains the number of words in the Answer n (1 ≤ n ≤ 1000). Each of the next n lines contains one of these words. The total length of all words doesn't exceed 10000.

    Output

    The first line of the output should contain two space-separated integers l and k, where l is the length of the longest possible regular bracket sequence and k is the number of words it consists of. The second line should contain k space-separated numbers of used words in the order they should be concatenated. Words are numbered from 1 to n in the order they are given in the input. If there are several possible answers output any of them.

    Samples

    inputoutput
    4
    (
    (((
    (
    ))
    
    4 3
    1 3 4
    
    3
    ()
    (()
    )
    
    6 3
    2 3 1
    
    Problem Author: Damir Akhmetzyanov
    Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
    To submit the solution for this problem go to the Problem set: 1745. Yet Another Answer