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 JAVA):

Solution:

import java.util.*;

public class C
{
   public static void main(String[] args)
   {
      new C(new Scanner(System.in));
   }

   public C(Scanner in)
   {
      String s = in.next();
      ArrayList<Node> vs = new ArrayList<Node>();
      int i=0;
      vs.add(new Node(i, 1));
      for (char c : s.toCharArray())
      {
         i++;
         if (c == '(')
            vs.add(new Node(i, 0));
         else
            vs.add(new Node(i, 1));
      }

      int best = 0;
      int cnt = 1;
      ArrayDeque<Node> stk = new ArrayDeque<Node>();
      for (Node n : vs)
      {
         if ((n.v == 0)||(stk.size() == 0))
            stk.push(n);
         else
         {
            Node tv = stk.pop();
            if (tv.v != 0)
            {
               stk.push(tv);
               stk.push(n);
               continue;
            }

            Node pp = stk.pop(); stk.push(pp);
            int len = n.i-pp.i;
            if (best == len)
               cnt++;
            else if (len > best)
            {
               best = len;
               cnt = 1;
            }
         }
      }

      System.out.printf("%d %d%n", best, cnt);
   }
}

class Node
{
   int i;
   int v;

   public Node(int a, int b)
   {
      i = a;
      v = b;
   }
}