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:
parentheses = raw_input()

stack = []

a = [-1]*1000005
b = [-1]*1000005

biggest_substring = -1
number_of_substrings = -1

for paren in range(len(parentheses)):
	if parentheses[paren]=="(":
		stack.append(paren)
	else:
		if len(stack)==0:
			a[paren] = -1
			b[paren] = -1
		else:
			starting_parentheses = stack.pop()
			a[paren] = starting_parentheses
			if starting_parentheses == 0:
				b[paren] = 0
			else:
				if parentheses[a[paren]-1] == ")" and b[a[paren]-1] != -1:
					b[paren] = b[a[paren]-1]
				else:
					b[paren] = starting_parentheses
	if b[paren] != -1:
		substring_length = (paren-b[paren])+1
		if biggest_substring < substring_length:
			biggest_substring = substring_length
			number_of_substrings = 1
		elif substring_length == biggest_substring:
			number_of_substrings += 1
			
if biggest_substring == -1:
	print "0 1"
else:
	print "%d %d" % (biggest_substring, number_of_substrings)