Problem: This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not. 

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

Input

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Examples

Input

)((())))(()())


Output

6 2


Input

))(


Output

0 1

Solution (in PYTHON):

Solution:


def main():
    seq = list(raw_input())
    dp_keep = [0 for i in range(1000010)]
    stc = []
    maxim, counts = 0, 0



    for i in range(len(seq)):
        if(seq[i] == '('):
            stc.append(i)
            dp_keep[i] = -1

        else:
            if(not len(stc)):
                dp_keep[i] = -1
            else:
                val = stc.pop()
                dp_keep[i] = val

                if(val > 0  and  seq[val-1] == ')'  and  dp_keep[val-1] != -1):
                    dp_keep[i] = dp_keep[val-1]


    for i in range(len(seq)):
        if(seq[i] == ')'  and  dp_keep[i] != -1):
            value = i-dp_keep[i]+1
            
            if(maxim < value):
                maxim = value
                counts = 1
                
            elif(maxim == value):
                counts += 1
    


    if(maxim == 0):
        print "0 1"
    else:
        print maxim, counts
        
##########################################
##########################################
##########################################
if(__name__ == "__main__"):
    main()