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;
char buf[1000005];
int len;
int cors[1000005];
int far[1000005];
void input() { cin >> buf; }
void solve() {
  len = strlen(buf);
  memset(cors, -1, sizeof(cors));
  memset(far, -1, sizeof(far));
  stack<int> stk;
  int pre;
  int maxl, cnt;
  for (int i = (0), _n = (len - 1); i <= _n; ++i) {
    if (buf[i] == '(') {
      stk.push(i);
    } else {
      if (!stk.empty()) {
        cors[i] = stk.top();
        stk.pop();
        pre = cors[i] - 1;
        if (pre > 0 && buf[pre] == ')' && far[pre] != -1)
          far[i] = far[pre];
        else
          far[i] = cors[i];
      }
    }
  }
  maxl = 0;
  cnt = 1;
  for (int i = (0), _n = (len - 1); i <= _n; ++i) {
    if (far[i] != -1) {
      if (i - far[i] + 1 > maxl) {
        maxl = i - far[i] + 1;
        cnt = 1;
      } else if (i - far[i] + 1 == maxl) {
        ++cnt;
      }
    }
  }
  printf("%d %d\n", maxl, cnt);
}
int main(void) {
  input();
  solve();
  return 0;
}