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()
diff = []
stk = []
for i in range(len(s)):
	if s[i] == '(':
		stk.append(i)
	else:
		if len(stk) != 0:
			diff.append([stk.pop(), i])
if len(diff) == 0:
	print 0, 1
else:
	diff.sort()
	hehe = []
	prevl, prevr = -2, -2
	sz = 0
	for i in diff:
		if prevl < i[0] and prevr > i[1]:
			continue
		elif prevr + 1 == i[0]:
			sz += i[1] - i[0] + 1
			prevr = i[1]
		else:
			hehe.append((prevl, prevr))
			prevl = i[0]
			prevr = i[1]
	hehe.append((prevl, prevr))
	#print hehe
	mx = 0
	cnt = 0
	for i in hehe:
		if i[1] - i[0] + 1 > mx:
			mx = i[1] - i[0] + 1
			cnt = 1
		elif i[1] - i[0] + 1 == mx:
			cnt += 1
	print mx, cnt