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:
def main():
       #get the input string
       string = input()
       #here we will store the indexes of coresponding opening bracket on the position of closing bracket
       correspondingOpen = [-2]*len(string)
       #here we will store the index of earliest opened parantesis which has a closign one
       earliestOpen = [-2]*len(string)
       #in the stack we will store the opening parantesis until we will find a closing one
       stack = []
       #for each character in string
       for i in range(len(string)):
              #if it is an opening one
              if string[i] == '(':
                     #put it in stack
                     stack.append(i)
              #if it is a closing one
              if string[i] == ')':
                     #and we don't have opened parantesis in the stack
                     if len(stack) == 0:
                            #then it does not correspond it looks like this ))() 
                            #so we have no corresponding opening parantesis
                            correspondingOpen[i] = -1
                            #and no parantesis to the left
                            earliestOpen[i] = -1
                     else:#the stack is not empty
                            #remove the last parantesis from the stack because it corresponds to the opening parantesis of the current closing one
                            correspondingOpen[i] = stack.pop()
                            #if from the left we have a closing parantesis that has a opening one, then we have a whole correct sequence
                            if correspondingOpen[i] - 1 >=0 and string[correspondingOpen[i] - 1] == ')' and earliestOpen[correspondingOpen[i] - 1] != -1:
                                   #the index of earliest open starts from the left
                                   earliestOpen[i] = earliestOpen[correspondingOpen[i] - 1]
                                   earliestOpen[correspondingOpen[i] - 1] = -2
                            else:
                                   #if we dont have other correct index to the left, just leave the starting index as it was
                                   earliestOpen[i] = correspondingOpen[i]
       maxLength = 0
       countSequences = 0
       length=[]
       i = len(string)-1
       #go from the right to left
       while i >= 0:
              #if we find a sequence 
              if earliestOpen[i] >= 0:
                     #and it's length is greater than maxLength
                     if (i - earliestOpen[i] + 1) > maxLength:
                            #update maxLength
                            maxLength = i - earliestOpen[i] + 1
                     #store all lengths in a list
                     length.append(i - earliestOpen[i] + 1)
                     #jump with len(sequence) to the left, in order to avoid counting embrecated sequences
                     i =  earliestOpen[i]
              i -= 1
       #count the number of sequences with max length
       for i in range(len(length)):
              if maxLength == length[i]:
                     countSequences += 1
       #problem condition
       if countSequences == 0:
              countSequences = 1
       print(maxLength,countSequences)
main()