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:
#https://codeforces.com/contest/5/problem/C

#SC = TC = o(n)

s = input().strip()

stack = []

valid = []

for k in range(len(s)):
	#push ( 
	if s[k]=='(':
		stack.append(k)
	elif s[k]==')':
		#if empty stack dont push ) because no ( in stack
		if not stack:
			pass
		else:
			popped = stack.pop()
			valid.append((popped,k))	#push start,end index of valid () pair

#start from end of valid . see pdf for explanation
num_substr = 0
maxlen = 0

if valid: 
	prev = valid[-1] 
for k in range(len(valid)-2, -1, -1):
	#check if current is container or adjacent to  previous
	if (prev[0]<valid[k][0] and prev[1]>valid[k][1]):	#container
		prev = prev
	elif (prev[0]==valid[k][1]+1):	#adjacent
		prev = (valid[k][0], prev[1])	#prev will always be bigger cos starting from end
	else:	#one substring territory has ended
		t = prev[1]-prev[0]+1	#calculate length of substr
		if t>maxlen:	#if len greater than max update
			maxlen = t
			num_substr = 1	#reset count to 1
		elif t==maxlen:	#if same just increase count
			num_substr += 1
		prev = valid[k]	#update previous. new substr will begin with current
		#one substr ended with previous

#increase substring count at last for last substring 
if valid:
	t = prev[1]-prev[0]+1
	if t>maxlen:
		maxlen = t 
		num_substr = 1
	elif t==maxlen:
		num_substr += 1

if num_substr == 0:
	num_substr = 1	#as question demands else illogical

print('{} {}'.format(maxlen, num_substr))