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;
struct pairvar {
  int a;
  int b;
};
bool isPrime(long long x) {
  if (x == 1) {
    return false;
  }
  long long a = (long long)x;
  for (int i = 2; i <= (long long)sqrt((double)a); i++) {
    if (a % i == 0) {
      return false;
    }
  }
  return true;
}
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long factorial(long long x) {
  long long sum = 1;
  for (long long i = 1; i <= x; i++) {
    sum *= i;
  }
  return sum;
}
int toint(string s) {
  int x = 0;
  int k = (int)pow(10, (double)s.length() - 1);
  for (int i = 0; i < (int)s.length(); i++) {
    x += (s[i] - '0') * k;
    k /= 10;
  }
  return x;
}
string tostr(int x) {
  if (x == 0) {
    return "0";
  }
  string s = "";
  bool f = x < 0;
  x = abs(x);
  while (x != 0) {
    s += (x % 10) + '0';
    x /= 10;
  }
  string t = "";
  if (f) {
    t = "-";
  }
  for (int i = s.length() - 1; i >= 0; i--) {
    t += s[i];
  }
  return t;
}
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
string tobin(int a) {
  string s;
  while (a != 0) {
    s += '0' + (a % 2);
    a /= 2;
  }
  string r = "";
  for (int i = s.length() - 1; i >= 0; i--) {
    r += s[i];
  }
  return r;
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first) {
    return a.second < b.second;
  }
  return a.first < b.first;
}
int dp[1000005];
int t[1000005];
int main() {
  string s;
  getline(cin, s);
  stack<pair<int, int>> cnt;
  vector<pair<int, int>> sgm;
  int n = s.size();
  t[n];
  for (int i = 0; i < n; i++) {
    t[i] = 0;
  }
  dp[n];
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == ')') {
      k--;
    } else {
      k++;
    }
    dp[i] = k;
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == ')') {
      if (cnt.size() != 0) {
        int ind = cnt.top().second;
        cnt.pop();
        if (ind == 0) {
          sgm.push_back(make_pair(ind, i));
        } else {
          if (dp[ind - 1] == dp[i]) {
            sgm.push_back(make_pair(ind, i));
          }
        }
      }
    } else {
      cnt.push(make_pair(dp[i], i));
    }
  }
  if (sgm.size() == 0) {
    cout << "0 1";
    return 0;
  }
  sort(sgm.begin(), sgm.end(), cmp);
  int l = sgm[0].first;
  int r = sgm[0].second;
  for (int i = 1; i < sgm.size(); i++) {
    if (r < sgm[i].first) {
      for (int e = l; e <= r; e++) {
        t[e] = 1;
      }
      l = sgm[i].first;
      r = sgm[i].second;
    } else {
      r = max(r, sgm[i].second);
    }
  }
  for (int e = l; e <= r; e++) {
    t[e] = 1;
  }
  map<int, int> ans;
  ans[0] = 1;
  for (int i = 0; i < n; i++) {
    if (t[i] == 1) {
      int k = 0;
      int j = i;
      while (t[j] != 0 && j < n) {
        j++;
        k++;
      }
      i = j;
      ans[k]++;
    }
  }
  int t1 = 0;
  int t2 = 0;
  for (auto j : ans) {
    if (j.first > t1) {
      t1 = j.first;
      t2 = j.second;
    }
  }
  cout << t1 << " " << t2;
  return 0;
}