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.*;
import java.lang.*;
import java.io.*;

public class Temp {
	static int imax = Integer.MAX_VALUE, imin = Integer.MIN_VALUE;
	static long lmax = Long.MAX_VALUE, lmin = Long.MIN_VALUE;
	static long mod = (long) 1e9 + 7;

	public static void main(String[] args) throws java.lang.Exception {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		// int test=in.ni();
		int test = 1;
		int i = 0, j = 0;
		while (test-- > 0) {
			char str[] = in.ncs();
			int n = str.length;
			Stack<Pair> st = new Stack<>();
			// System.out.println(n);
			ArrayList<Pair> list = new ArrayList<>();
			for (i = 0; i < n; i++) {
				if (str[i] == '(') {
					st.add(new Pair(str[i], i));
				} else {
					if (st.isEmpty() || (char) st.peek().x != '(') {
						st.clear();
					} else {
						list.add(new Pair(st.pop().y, i));
					}
				}
			}
			Collections.sort(list, new Comparator<Pair>() {
				public int compare(Pair ob1, Pair ob2) {
					return ob1.x - ob2.x;
				}
			});
			i = 0;
			ArrayList<Pair> list1 = new ArrayList<>();
			while (i < list.size()) {
				Pair ob = list.get(i);
				i++;
				while (i < list.size() && list.get(i).y < ob.y) {
					i++;
				}
				list1.add(ob);
			}
			i = 0;
			HashMap<Integer, Integer> map = new HashMap<>();
			map.put(0, 1);
			int cnt = 0, ans = 0;
			while (i < list1.size()) {
				cnt = 0;
				while ((i + 1 < list1.size()) && (list1.get(i).y + 1 == list1.get(i + 1).x)) {
					// System.out.println(list1.get(i).y +" "+ list1.get(i).x );
					cnt += list1.get(i).y - list1.get(i).x + 1;
					i++;
				}
				cnt += list1.get(i).y - list1.get(i).x + 1;
				// System.out.println(list1.get(i).y +" "+ list1.get(i).x +"
				// "+cnt);
				i++;
				if (cnt > ans) {
					ans = cnt;
				}
				if (map.get(cnt) == null) {
					map.put(cnt, 1);
				} else {
					map.put(cnt, map.get(cnt) + 1);
				}
			}
			// System.out.println(list);
			// System.out.println(list1);
			out.println(ans + " " + map.get(ans));
		}
		out.close();
	}

	static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}
	}

	static void print(int arr[], int len) {
		for (int i = 0; i < len; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	static class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int ni() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c & 15;
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c & 15;
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String ns() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public char[] ncs() {
			return ns().toCharArray();
		}

		public String nLine() {
			int c = read();
			// while (c != '\n' && c != '\r' && c != '\t' && c != -1)
			// c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (c != '\n' && c != '\r' && c != '\t' && c != -1);
			return res.toString();
		}

		public static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

	}

}