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

cases = False

# Pre-defined function
# Begin
def fast_pow(a:int, b:int):
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

def c2(n):
    return n * (n-1) // 2

def get():
    return list(map(int, input().split()))

def bits(n: int):
    return list(bin(n)).count('1')

def main(test_case = False):
    n = int(input()) if test_case else 1
    for _ in range(n):
        test()

def flush():
    sys.stdout.flush()

def parr(arr):
    print(*arr, sep=' ')

def gcd(a, b):
    while b:
        if b % a == 0:
            break
        tmp = a
        a = b % a
        b = tmp
    return a

def ext_gcd(a: int, b: int):
    if (b == 0):
        return [a, [1, 0]]
 
    res = ext_gcd(b, a % b)
    g = res[0]
    x1 = res[1][0]
    y1 = res[1][1]
    x = y1
    y = x1 - y1 * (a // b)
 
    return [g, [x, y]]

# End

stack, pair, first = [], [], []

def test():
    global stack, pair, first
    s = list(input())
    n = len(s)
    pair = [-1] * n
    first = [-1] * n
    
    i = 0
    while i < n:
        if s[i] == '(':
            stack.append(i)
        else:
            if stack:
                d = stack.pop()
                pair[i] = d
                first[i] = d
                if pair[i] > 0 and first[pair[i] - 1] != -1:
                    first[i] = first[pair[i] - 1]
            else:
                pair[i] = -1
                first[i] = -1
        i += 1
    
    i = 0
    mx = 0
    cnt = 1
    while i < n:
        if first[i] == -1:
            i +=1
            continue
        ln = i - first[i] + 1
        # print(i, ln)
        if ln > mx:
            mx = ln
            cnt = 1
        elif ln == mx:
            cnt += 1
        i += 1
    
    # print(stack)
    # print(pair)
    # print(first)
    print(mx, cnt)

main(cases)