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:
def checker(string):
    n = len(string)
    # Create a stack and push -1 as initial index into it. It is base case
    stack = [-1]

    # Initialize results
    max_value = 0
    max_count = 1
    # Traverse all characters of given string
    for i in range(n):

        # If opening bracket, push index of it into stack
        if string[i] == '(':
            stack.append(i)

        # if there is closing bracket and stack isn't empty, then pop the stack value (opening bracket)
        # find length and calculate results
        elif len(stack) > 1:
            # to count length correctly we have to pop our last value. Otherwise, we won't include our opening bracket in length
            # also, we need to match brackets, so pop with stack is a good way to "eliminate" balanced pair of brackets
            stack.pop()
            # current index (closing brackets) - last index in stack (opening brackets)
            length = i - stack[-1]
            # if our current length and max length are equal, then add to max length count.
            if length == max_value:
                max_count += 1
            # if our length is higher, then reset max length count and replace max value
            elif length >= max_value:
                max_value = length
                max_count = 1
        # if there is nothing in our stack, then make start value current index to continue our max length check
        else:
            stack[0] = i

    return max_value, max_count


s = input()
max_value, max_count = checker(s)
print(max_value, max_count)