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
input = sys.stdin.readline
def I():return input().strip()
def II():return int(input().strip())
def LI():return [*map(int,input().strip().split())]
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter

inp = I()
size = len(inp)
dp = [0] * (size + 1)
que = deque()
for i in range(1, size + 1):
    if inp[i - 1] == '(':
        que.append(i)
    else:
        if que:
            pop = que.pop()
            dp[i] = i - pop + 1 + dp[pop - 1]
mex = max(dp)
cnt = dp.count(mex)
if not mex:
    print(0, 1)
else:
    print(mex, cnt)