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;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 1 << 29;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n >> b) & 1; }
inline void set_bit(int& n, int b) { n |= two(b); }
inline void unset_bit(int& n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) {
  int res = 0;
  while (n && ++res) n -= n & (-n);
  return res;
}
template <class T>
void chmax(T& a, const T& b) {
  a = max(a, b);
}
template <class T>
void chmin(T& a, const T& b) {
  a = min(a, b);
}
const int MOD = 1000000007;
bool isPowerOfTwo(long long int x) { return x && (!(x & (x - 1))); }
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
int highestPowerof2(unsigned int n) {
  if (n < 1) return 0;
  int res = 1;
  for (int i = 0; i < 8 * sizeof(unsigned int); i++) {
    int curr = 1 << i;
    if (curr > n) break;
    res = curr;
  }
  return res;
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
int E[1000001], S[1000001], F[1000001];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  while (t--) {
    string s;
    cin >> s;
    stack<int> stk;
    for (int i = 0; i < 1000001; i++) F[i] = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s[i] == '(')
        stk.push(i);
      else {
        if (stk.empty())
          S[i] = -1;
        else {
          int tp = stk.top();
          stk.pop();
          S[i] = tp;
          E[i] = tp;
          if (tp >= 1 && s[tp - 1] == ')' && S[tp - 1] != -1) {
            E[i] = E[tp - 1];
          }
          F[i - E[i] + 1]++;
        }
      }
    }
    int mx = -1;
    for (int i = 0; i < 1000001; i++) {
      if (F[i] != 0) {
        mx = max(mx, i);
      }
    }
    if (mx == -1)
      cout << "0 1\n";
    else {
      cout << mx << " " << F[mx] << "\n";
    }
  }
  return 0;
}