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

Solution:
#include <bits/stdc++.h>
char c[1010000];
int n, zhan[1010000], max = 0, x = 1;
struct s_node {
  int s, e;
  s_node *next;
} * head;
void insert(int s, int e) {
  s_node *p = new s_node;
  p->next = head;
  head = p;
  p->s = s;
  p->e = e;
  bool done = true;
  while (done) {
    done = false;
    while (p->next != NULL && (p->next)->e == p->s - 1)
      p->s = (p->next)->s, p->next = (p->next)->next, done = true;
    while (p->next != NULL && (p->next)->e < p->e && (p->next)->s > p->s)
      p->next = (p->next)->next, done = true;
  }
  if (max == p->e - p->s + 1) x++;
  if (max < p->e - p->s + 1) max = p->e - p->s + 1, x = 1;
}
void doit() {
  int e = 0, t = 0;
  while (e < n) {
    if (c[e] == '(')
      zhan[++t] = e;
    else if (t)
      insert(zhan[t--], e);
    e++;
  }
  printf("%d %d", max, x);
}
int main() {
  scanf("%s", c);
  n = strlen(c);
  doit();
  return 0;
}