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:
#https://codeforces.com/contest/5/problem/C

def empty(l):
    return len(l) == 0

def longest_regular_bracket_sequence(str):
    st = []

    for ch in str:
        if ch == '(':
            st.append(('O', -1))
        else:
            valid_seq = False
            s = 0
            while not empty(st):
                (t, l) =  st.pop()
                if t == 'O':
                    valid_seq = True
                    s += 2
                    break
                elif t == 'R':
                    s += l
                else:
                    st.append(('C', -1))
                    break
            if s != 0:
                st.append(('R', s))
            if not valid_seq:
                st.append(('C', -1))

    # print(st)

    l = 0
    ml = 0
    cnt = 0
    
    while not empty(st):
        (t, l1) = st.pop()
        if t == 'R' and l1 != 0:
            l += l1
            if l == ml:
                cnt += 1
            elif l > ml:
                ml = l
                cnt = 1
        else:
            l = 0

    if ml == 0:
        cnt = 1

    return (ml, cnt)


s = input()
(ml, cnt) = longest_regular_bracket_sequence(s)
print(ml, cnt)