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 PYTHON3):

Solution:
# program to find longest regular bracket sequence and their counts
# 
def LongestBracketSequence(s):
    """function calculates the longest bracket sequence and their counts when s string is given"""
    stack = []
    arr = [0]*len(s)
    max, sum, count = [0, 0, 0]
    longest_count = 0
    for i in range(len(s)):
        ch = s[i]
        if ch == '(':
            stack.append('(')
        elif ch == ')' and len(stack) != 0:
            top = stack[-1]
            if top == '(':
                stack.pop()
                arr[i] = 2

    for value in reversed(arr):
        if value == 2:
            if count < 0:
                count = 1
                if max < sum:
                    max = sum
                    longest_count = 1
                elif max == sum:
                    longest_count += 1
                sum = 2
            else:
                count += 1
                sum += 2
        else:
            count -= 1
            if count == -1:
                if max < sum:
                    max = sum
                    longest_count = 1
                elif max == sum:
                    longest_count += 1
                sum = 0
    
    if count == 0 and sum > 0:
        if max < sum:
            max = sum
            longest_count = 1
        elif max == sum:
            longest_count += 1
    if max == 0:
        longest_count = 1
    print(str(max) + ' ' + str(longest_count))


s = input()
LongestBracketSequence(s)