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:
"""
 
         _nnnn_                      
        dGGGGMMb     ,''''''''''''''''''''''.
       @p~qp~~qMb    | Promoting GNU/Linux  |
       M|@||@) M|   _;......................'
       @,----.JM| -'
      JS^\__/  qKL
     dZP        qKRb
    dZP          qKKb
   fZP            SMMb
   HZM            MMMM
   FqM            MMMM
 __| ".        |\dS"qML
 |    `.       | `' \Zq
_)      \.___.,|     .'
\____   )MMMMMM|   .'
     `-'       `--' hjm
 
"""

inp = input()

maxlen, occur, stack = 0, 1, [-1]

for i, val in enumerate(inp):
    if val == '(': stack.append(i)
    elif len(stack) > 1:
        stack.pop()
        consq = i - stack[-1]
        if maxlen < consq: maxlen, occur = consq, 1
        elif maxlen == consq:
            occur += 1
    else:
        stack[0] = i

print(maxlen, occur)