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>
using namespace std;
string brk;
int mx = 0;
int tms = 1;
map<int, int> lt;
int acum[1000005];
int mem[1000005];
bool usd[1000005];
int close[10000005];
int dp(int i) {
  if (usd[i]) {
    return mem[i];
  }
  if (i > brk.size() or brk[i - 1] == ')') {
    usd[i] = 1;
    return mem[i] = 0;
  }
  int cl = close[i];
  if (cl < i) {
    usd[i] = 1;
    return mem[i] = 0;
  }
  mem[i] = cl - i + 1 + dp(cl + 1);
  usd[i] = 1;
  return mem[i];
}
int main() {
  cin >> brk;
  int sal = 0, tam;
  lt[0] = 1;
  for (int i = 0; i < brk.size(); i++) {
    if (brk[i] == '(') {
      lt[sal] = i + 2;
      acum[i + 1] = ++sal;
    } else {
      acum[i + 1] = --sal;
      if (lt[sal]) {
        close[lt[sal] - 1] = i + 1;
      }
    }
  }
  for (int i = 1; i <= brk.size(); i++) {
    sal = dp(i);
    if (sal > mx) {
      mx = mem[i];
      tms = 1;
    } else if (mx and mem[i] == mx) {
      tms++;
    }
  }
  cout << mx << " " << tms << endl;
  return 0;
}