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:
string = input()

close_ = open_= max_len = 0

counter = 1

dp = [True] * len(string)


for idx in range(len(string)):
	if string[idx] == "(":
		open_ += 1
	else:
		close_ += 1
	if open_ == close_:
		len_ = 2 * open_
		if len_ > max_len:
			max_len, dp[idx - len_ + 1], counter = len_, False, 1
		elif len_ == max_len:
			dp[idx - len_ + 1] = False
			counter += 1		
	elif close_ > open_:
		close_ = open_ = 0


close_ = open_= 0


for idx in range(len(string))[::-1]:
	if string[idx] == "(":
		open_ += 1
	else:
		close_ += 1
	if open_ == close_:
		len_ = 2 * open_
		if len_ > max_len:
			max_len, counter = len_, 1
		elif len_ == max_len:
			if dp[idx]:
				counter += 1
	elif open_ > close_:
		close_ = open_= 0
print(max_len, counter)