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:
from sys import stdin

s = stdin.readline().strip()

best = 0
cnt  = 1

stack = []

for c in s:
    if c == '(':
        stack.append(('(', 1))
    else:
        span = 2
        success = False
        while (stack):
            (t, w) = stack.pop()
            if t == '(': 
                success = True
                break;
            else:
                span += w
        if success:
            while (stack):
                (t, w) = stack.pop()
                if t == '(':
                    stack.append((t, w))
                    break
                else:
                    span += w
            stack.append(('()', span))
            if span > best:
                best = span
                cnt = 1
            elif span == best:
                cnt += 1

print(str(best) + " " + str(cnt))