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.Scanner;
import java.util.Stack;

public class CopyOfCF5C {
  private static int[] solve(String sequence) {
    int l = sequence.length();
    int[] len = new int[l];
    int max = 0;
    int cnt = 0;
    for (int i = l - 1; i >= 0; i--) {
      if (sequence.charAt(i) == ')') {
        continue;
      }
      int cur = 1;
      int j;
      for (j = i + 1; j < l; j++) {
        if (sequence.charAt(j) == '(') {
          if (len[j] == 0) {
            break;
          }
          j = j + len[j] - 1;
        } else {
          cur--;
          if (cur < 0) {
            break;
          }
        }
      }
      if (cur <= 0) {
        len[i] = j - i;
      }
      if (max < len[i]) {
        max = len[i];
        cnt = 1;
      } else if (max == len[i]) {
        cnt++;
      }
    }
    return new int[] {max, max == 0 ? 1 : cnt};
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] ans = solve(sc.nextLine());
    sc.close();
    System.out.println(ans[0] + " " + ans[1]);
  }
}