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.*;

public class Main {

  public static void main(String args[]) {
    (new Main()).solve();
  }

  void solve() {

    Scanner cin = new Scanner(System.in);

    while( cin.hasNext() ) {

      String s = cin.next();
      int n = s.length();

      ArrayList<int[]> all = new ArrayList<int[]>();
      int L = -1;
      int R = -1;

      for(int i=0; i<n; ++i) {
        if( s.charAt(i) == '(' ) {
          if( i + 1 < n && s.charAt(i + 1) == ')' ) {
            int CL = i;
            int CR = i + 1;
            while( CL - 1 >= 0 ) {
              if( CL - 1 == R ) {
                CL = L;
                if( all.size() > 0 ) {
                  int tmp[] = all.remove(all.size() - 1);
                  L = tmp[0];
                  R = tmp[1];
                }
                else {
                  L = -1;
                  R = -1;
                }
                continue;
              }
              if( CR + 1 < n && s.charAt(CL - 1) == '(' && s.charAt(CR + 1) == ')' ) {
                --CL;
                ++CR;
                continue;
              }
              break;
            }
            if( R >= 0 ) { all.add(new int[] { L, R }); }
            L = CL;
            R = CR;
            i = CR;
          }
        }
      }

      if( R >= 0 ) { all.add(new int[] { L, R }); }

      int size = 0;
      int count = 1;

      for(int p[] : all) {
        int S = p[1] - p[0] + 1;
        if( S > size ) {
          size = S;
          count = 1;
        }
        else if( S == size ) { ++count; }
      }

      System.out.println(size + " " + count);

    }

  }

}