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 JAVA):

Solution:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

       public static void main(String[] args) {
                String s;
                Scanner sc = new Scanner(System.in);
                ArrayList<Integer> pos = new ArrayList<Integer>();
                s = sc.next();
                int maxi = 0, count=1;
                //init
                int [] a = new int [1000009];
                for (int i =0 ; i <= s.length(); i++)
                {
                    a[i] = s.length() +1;
                }
                for (int i = 0; i < s.length(); i++)
                    if (s.charAt(i) == ')')
                    {
                        if (pos.isEmpty())
                        {
                            continue ;
                        }

                        a[i] = pos.get(pos.size()-1);
                        if (pos.get(pos.size()-1)>0)
                            a[i] = Math.min(a[i],a[pos.get(pos.size()-1)-1]);

                        if (i- a[i]  +1 > maxi)
                        {
                            maxi =i-a[i] +1 ;
                            count = 1 ;
                        }
                        else
                        if (i-a[i] +1 == maxi)
                        {
                            count +=1 ;
                        }
                        pos.remove(pos.size()-1);
                    }
                    else
                        pos.add(i);
                    System.out.println(maxi+" "+count);
            }

}