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:
# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/6/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(s):
    c = 0
    ans, tmp, count = 0, 0, 0
    for i, v in enumerate(s):
        if v == '(':
            c += 1
        else:
            c -= 1
            if c >= 0:
                tmp += 1
            else:
                if tmp > ans:
                    ans = tmp
                    count = 1
                elif tmp > 0 and tmp == ans:
                    count += 1
                tmp = 0
                c = 0
    if c == 0:
        if tmp > ans:
            ans = tmp
            count = 1
        elif tmp > 0 and tmp == ans:
            count += 1
            
    return ans * 2, max(count, 1)
    
            
    
s = input()
a, b = solve(s)
c, d = solve(['(' if v ==')' else ')' for v in s[::-1]])
if a > c or (a == c and b >= d):
    print('{} {}'.format(a, b))
else:
    print('{} {}'.format(c, d))