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 PYTHON):

Solution:
s = raw_input().split()[0]
stack = [-1]
for i in xrange(len(s)):
	if s[i] == ')' and len(stack) > 1 and s[stack[-1]] == '(':
		stack.pop()
	else:
		stack.append(i)
stack.append(len(s))
length, count = stack[0], 1
for i in xrange(1,len(stack)):
	if stack[i]-stack[i-1]-1 > length:
		length, count = stack[i]-stack[i-1]-1, 1
	elif stack[i]-stack[i-1]-1 == length and length != 0:
		count += 1
# print stack
print length, count