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;

public class test {
  private static int[] solve(String sequence) {
    int l = sequence.length();
    int[] len = new int[l + 1];
    int max = 0;
    int cnt = 0;
    for (int i = 2; i <= l; i++) {
      if (sequence.charAt(i - 1) == '(') {
        len[i] = 0;
      } else if (sequence.charAt(i - 2) == '(') {
        len[i] = 2 + len[i - 2];
      } else if (i - len[i - 1] - 2 < 0 || sequence.charAt(i - len[i - 1] - 2) == ')') {
        len[i] = 0;
      } else {
        len[i] = 2 + len[i - 1] + len[i - len[i - 1] - 2];
      }
      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]);
  }
}