Alternative Bracket Notation

A bracket string is balanced when every opening bracket has a matching closing bracket later in the string. A closing bracket matches the most recent opening bracket that is still unmatched.

Define an alternative bracket notation as follows. Every bracket pair gets one header of the form "start,end:". The values start and end are indices into the new notation string itself, not into the original string. The index start is the index of the character right after the ':' of that header. The index end is the index just past the end of the header of the last bracket pair contained in this pair. Cutting the new string from start up to end therefore gives an alternative bracket notation that describes every bracket pair contained inside this pair. An empty bracket pair contains nothing, so its start and end are equal.

Headers are listed in the order in which their opening brackets appear in the original string.

Each index takes up as many characters as it does when written in base 10. The index 42, for example, takes up 2 characters. Indices of the new string start at 0, and every index in the notation is an absolute index counted from the beginning of the new string.

Take the bracket string (()). Its alternative bracket notation is 4,8:8,8:. There are two bracket pairs, the outer one and the inner one. The outer opening bracket comes first, so the outer header 4,8: comes before the inner header 8,8:. The outer header occupies indices 0 to 3, so its start is 4, and the inner header occupies indices 4 to 7, so the outer end is 8. Cutting the new string from index 4 up to index 8 gives 8,8:, which describes what the outer bracket pair contains. The string 5,11:11,11: also obeys the rules, but the answer has to be the shortest notation, so 4,8:8,8: is correct.

The input is a single line holding a string s made only of opening and closing brackets. The length of s is between 2 and 4,000. There are no spaces. The string s is guaranteed to be balanced.

Print s in the alternative bracket notation on one line. When s has more than one valid notation, print the shortest one. The shortest notation is unique.