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:
__author__ = 'William'
count = 1         #number of times it appears
size = 0         #size of string
LengthStart = -1           #

input = raw_input()
array = []
for i in range(len(input)): #for every value
    if input[i] == '(':                          #append '('
        array.append(i)
    elif array:  # It's a ')' and the array isn't empty
        array.pop()        #removes last element
        if array:          #if the array is not empty
            tempsize = i - array[-1] # L equals the num of the item - the value of the last known ')', getting the size
        else:
            tempsize = i - LengthStart          # tempsize = LengthStart minus last known i
        if tempsize > size:            #if tempsize is larger than current largest, size is new tempsize
            size = tempsize
            count = 1               #reset count to 1
        elif tempsize == size: #if tempsize equals size at this point, they're the same length and increment count
                count+=1
    else:
        LengthStart = i #if we don't currently have a value in the array but it's  a ')', update the start point
print size, count