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 long long MOD = 1e9 + 7;
bool cmp(long long X, long long Y) { return X > Y; }
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long modpow(long long a, long long b, long long m = MOD) {
  a %= m;
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
long long bpow(long long a, long long b) {
  if (b < 0) {
    return 0;
  }
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long modinv(long long a, long long m = MOD) { return modpow(a, m - 2, m); }
const long long N = 2e5 + 2;
const long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long par[N];
long long szz[N];
long long find_set(long long v) {
  if (v == par[v]) {
    return v;
  }
  return par[v] = find_set(par[v]);
}
void make_set(long long v) {
  par[v] = v;
  szz[v] = 1;
}
void union_sets(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (szz[a] < szz[b]) {
      swap(a, b);
    }
    par[b] = a;
    szz[a] += szz[b];
  }
}
long long lef[N], rig[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  stack<long long> a;
  long long n = s.length();
  long long d[n], c[n];
  memset(d, -1, sizeof(d));
  memset(c, -1, sizeof(c));
  for (long long i = 0; i < n; i++) {
    if (s[i] == '(') {
      a.push(i);
    } else {
      if (a.empty()) {
        d[i] = -1;
        c[i] = -1;
      } else {
        long long k = a.top();
        a.pop();
        d[i] = k;
        c[i] = k;
        if (k > 0 && s[k - 1] == ')') {
          if (c[k - 1] != -1) {
            c[i] = min(c[i], c[k - 1]);
          }
        }
      }
    }
  }
  long long ans = 0;
  map<long long, long long> cnt;
  for (long long i = 0; i < n; i++) {
    if (c[i] != -1) {
      long long k = i - c[i];
      cnt[k]++;
    }
  }
  long long mx = 0;
  long long cn = 0;
  for (auto u : cnt) {
    if (u.first > mx) {
      mx = u.first;
      cn = u.second;
    }
  }
  if (mx == 0) {
    cout << 0 << " " << 1;
    return 0;
  }
  cout << mx + 1 << " " << cn;
}