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.

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.

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.