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:
# !/usr/bin/python

import sys

channel = sys.stdin
# channel = open("data.txt", 'r')

l = channel.readline()

brackets = [0]
# factors = [0]
len_sub_string = [0]

# factor_last = 0

for i in range(len(l)):
	if l[i] == "(":
		brackets.append(1)
		# factor_last += 1
		# factors.append(factor_last)
		len_sub_string.append(0)
		###############################
	elif l[i] == ")":
		if brackets[-1] == 1:
			last_idx = len(brackets)-1
			brackets.pop(last_idx)
			# factors.pop(last_idx)
			x = len_sub_string.pop(last_idx)+2
			len_sub_string[last_idx-1] += x
		else: # It's either first bracket or after another closing bracket
			brackets.append(-1)
			# factor_last += -1
			# factors.append(factor_last)
			len_sub_string.append(0)
	elif l[i] == "\n":
		break
	else:
		print len_sub_string
		print brackets
		print "Error. Here is the symbol:\n"
		print str(i) + " " + str(l[i]) 

		exit ()

max_br = 0
count = 1

for i in range(len(len_sub_string)):
	if len_sub_string[i] > max_br:
		max_br = len_sub_string[i]
		count = 1
	elif len_sub_string[i] == max_br and max_br != 0:
		count += 1

print str(max_br) + " " + str(count)


# channel.close()