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 void scan(int& i) { scanf("%d", &i); }
inline void scan(double& i) { scanf("%lf", &i); }
inline void scan(int64_t& i) { scanf("%" PRId64, &i); }
inline void scan(string& s) { cin >> s; }
inline void pr(string& s) { cout << s; }
inline void pr(int i) { printf("%d", i); }
inline void pr(bool b) { pr((int)b); }
inline void pr(double d) { printf("%.9lf", d); }
inline void prln() { putchar('\n'); }
inline void prsp() { putchar(' '); }
inline void pr(int64_t i) { printf("%" PRId64, i); }
inline void pr(size_t i) { printf("%zd", i); }
template <typename T>
inline void scan(vector<T>& v) {
  for (T& t : v) scan(t);
}
template <typename T>
inline void scan(T* a, int n) {
  while (n--) scan(*a++);
}
template <typename T>
inline void prsp(vector<T>& v) {
  for (T& t : v) pr(t), prsp();
}
template <typename T>
inline void prsp(T* a, int n) {
  while (n--) pr(*a++), prsp();
}
template <typename T>
inline void prln(vector<T>& v) {
  for (T& t : v) pr(t), prln();
}
template <typename T>
inline void prln(T* a, int n) {
  while (n--) pr(*a++), prln();
}
template <typename T>
inline void prln(vector<vector<T> >& v) {
  for (vector<T>& t : v) prsp(t), prln();
}
template <typename T, typename... Args>
inline void scan(T& first, Args(&... args)) {
  scan(first), scan(args...);
}
template <typename T, typename... Args>
inline void pr(T first, Args... args) {
  pr(first), prsp(), pr(args...);
}
template <typename T>
vector<T>& operator+=(vector<T>& v, T x) {
  v.push_back(x);
  return v;
}
template <typename T>
vector<T>& operator--(vector<T>& v) {
  v.pop_back();
  return v;
}
template <typename T>
vector<T>& operator--(vector<T>& v, int) {
  v.pop_back();
  return v;
}
template <typename T>
bool operator!(stack<T>& q) {
  return !q.empty();
}
template <typename T>
stack<T>& operator+=(stack<T>& v, T x) {
  v.push(x);
  return v;
}
template <typename T>
T operator--(stack<T>& v) {
  v.pop();
  return v.top();
}
template <typename T>
T operator--(stack<T>& v, int) {
  T t = v.top();
  v.pop();
  return t;
}
template <typename T>
bool operator!(queue<T>& q) {
  return !q.empty();
}
template <typename T>
queue<T>& operator+=(queue<T>& v, T x) {
  v.push(x);
  return v;
}
template <typename T>
T operator--(queue<T>& v) {
  v.pop();
  return v.front();
}
template <typename T>
T operator--(queue<T>& v, int) {
  T t = v.front();
  v.pop();
  return t;
}
template <typename T, typename U>
inline void smax(T& a, U b) {
  if (b > a) a = b;
}
template <typename T, typename U>
inline void smin(T& a, U b) {
  if (b < a) a = b;
}
template <typename T, typename U>
inline T gcd(T a, U b) {
  return __gcd(a, b);
}
inline void init();
const int MOD = 1E9 + 7;
const int INF = MOD;
int main() {
  init();
  cin.sync_with_stdio(0);
  string s;
  stack<int> st;
  st += 0;
  cin >> s;
  int ex = 0, co = 1;
  for (char c : s) {
    if (c == ')') {
      int k = st--;
      if (!st) {
        st.top() += k + 2;
        if (st.top() > ex)
          ex = st.top(), co = 1;
        else if (st.top() == ex)
          co++;
      }
    } else {
      st += 0;
    }
    if (!!st) st += 0;
  }
  pr(ex, co);
}
inline void init() {}