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():
       string = input()
       correspondingOpen = [-2]*len(string)
       earliestOpen = [-2]*len(string)
       stack = []
       for i in range(len(string)):
              if string[i] == '(':
                     stack.append(i)
              if string[i] == ')':
                     if len(stack) == 0:
                            correspondingOpen[i] = -1
                            earliestOpen[i] = -1
                     else:
                            correspondingOpen[i] = stack.pop()
                            if correspondingOpen[i] - 1 >=0 and string[correspondingOpen[i] - 1] == ')' and earliestOpen[correspondingOpen[i] - 1] != -1:
                                   earliestOpen[i] = earliestOpen[correspondingOpen[i] - 1]
                                   earliestOpen[correspondingOpen[i] - 1] = -2
                            else:
                                   earliestOpen[i] = correspondingOpen[i]

       maxLength = 0
       countSequences = 0
       length=[]
       i = len(string)-1
  
       while i >= 0:
              if earliestOpen[i] >= 0:
                     if (i - earliestOpen[i] + 1) > maxLength:
                            maxLength = i - earliestOpen[i] + 1
                     length.append(i - earliestOpen[i] + 1)
                     i =  earliestOpen[i]
              i -= 1

       for i in range(len(length)):
              if maxLength == length[i]:
                     countSequences += 1
       if countSequences == 0:
              countSequences = 1
       print(maxLength,countSequences)
main()