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 findMaxLen(string):
    n = len(string)
    c=1
    # Create a stack and push -1 as initial index to it.
    stk = []
    stk.append(-1)
 
    # Initialize result
    result = 0
 
    # Traverse all characters of given string
    for i in xrange(n):
     
        # If opening bracket, push index of it
        if string[i] == '(':
            stk.append(i)
 
        else:    # If closing bracket, i.e., str[i] = ')'
     
            # Pop the previous opening bracket's index
            stk.pop()
     
            # Check if this length formed with base of
            # current valid substring is more than max 
            # so far
            if len(stk) != 0:
                x=i - stk[len(stk)-1]
                if x>result:
                    result=x
                    c=1
                elif x==result:
                    c+=1
                result = max(result, i - stk[len(stk)-1])
 
            # If stack is empty. push current index as 
            # base for next valid substring (if any)
            else:
                stk.append(i)
    print result,c
   # return result

s=raw_input()
findMaxLen(s)