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:
s = input()
n = len(s)
dp = []
stack = []
ans = []
for i in range(n):
	if s[i]=="(":
		dp.append(i)
		stack.append(i)
		ans.append(i)
	else:
		if not stack:
			dp.append(-1)
			ans.append(-1)
			continue
		dp.append(stack[-1])
		if dp[-1]-1>=0 and s[dp[-1]-1]==")" and ans[dp[-1]-1]!=-1:
			ans.append(ans[dp[-1]-1])
		else:
			ans.append(dp[-1])
		stack.pop()

	# print (dp,ans)

# print (*ans)
maxx = 0
count = 1
for i in range(len(ans)):
	if i==ans[i]:
		continue
	diff = i-ans[i]+1
	if ans[i]!=-1 and diff>maxx:
		maxx = diff
		count = 1
	elif ans[i]!=-1 and diff==maxx:
		count += 1
# print (*dp)
print (maxx,count)