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;
const int N = (int)1e6 + 7;
int balance[N];
int n;
int numlog[N];
int table[21][N];
void build() {
  for (int i = 2; i <= n; i++) {
    numlog[i] = numlog[i >> 1] + 1;
  }
  for (int i = 0; i <= numlog[n]; i++) {
    for (int j = 0; j <= n; j++) {
      if (!i) {
        table[i][j] = balance[j];
        continue;
      }
      table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
    }
  }
}
int get(int l, int r) {
  int curlog = numlog[r - l + 1];
  return min(table[curlog][l], table[curlog][r - (1 << curlog) + 1]);
}
int base = 1e6;
vector<int> pos[N + N];
int pt[N + N];
int main() {
  string s;
  cin >> s;
  n = s.size();
  s = ' ' + s;
  for (int i = 1; i <= n; i++) {
    balance[i] = balance[i - 1] + ((s[i] == '(') ? 1 : -1);
  }
  build();
  pos[base].push_back(0);
  for (int i = 1; i <= n; i++) {
    pos[balance[i] + base].push_back(i);
  }
  pair<int, int> ans;
  ans.first = 0;
  ans.second = 1;
  int l, r, mid;
  pt[base] = 1;
  for (int i = 1; i <= n; i++) {
    l = 0;
    r = pt[balance[i] + base]++;
    int cur = balance[i] + base;
    while (r - l > 1) {
      mid = (l + r) >> 1;
      if (get(pos[cur][mid], i) < balance[i]) {
        l = mid;
      } else {
        r = mid;
      }
    }
    if (r > 0 && get(pos[cur][r - 1], i) >= balance[i]) {
      r--;
    }
    if (l <= r && pos[cur][r] != i) {
      if (i - pos[cur][r] > ans.first) {
        ans.first = i - pos[cur][r];
        ans.second = 1;
      } else if (i - pos[cur][r] == ans.first) {
        ans.second++;
      }
    }
  }
  cout << ans.first << ' ' << ans.second;
}