说明

时间限制：1 Sec 内存限制：256 MB 输入文件：emoticon.in 输出文件：emoticon.out

(^^*) 是小明自创的颜文字，分为朝左、朝右两种形态：

- 朝左：(^^*)

- 朝右：(*^^)

你是可以炼制颜文字的魔法师。

给定仅由 ( ^ * ) 构成的字符串 $S$，遵循以下规则炼制两种颜文字：

任选一个左括号（第 $a$ 位）、一个右括号（第 $e$ 位）

1. 若两者之间存在位置满足 $a<b<c<d<e$，字符依次为 $S[b]=$^，$S[c]=$^，$S[d]=$*，就能炼出 $1$ 个朝左(^^*)

2. 若两者之间存在位置满足 $a<b<c<d<e$，字符依次为 $S[b]=$*，$S[c]=$^，$S[d]=$^，就能炼出 $1$ 个朝右(*^^)

重要约束

同一个 ( 与 ) 配对 $(a,e)$，每种朝向最多只能炼 $1$ 个。

也就是说：同一组 $a,e$ 不能产出多个同方向颜文字；不同方向互不干涉。

字符可以被多个炼制组合重复复用。

我们把一组完整选取位置记作五元组 $(a,b,c,d,e)$。

举例说明

1. 字符串 (*^^*)

    - 取 $(1,3,4,5,6)$ → 炼制 $1$ 个朝左 (^^*)

    - 取 $(1,2,3,4,6)$ → 炼制 $1$ 个朝右 (*^^)

2. 字符串 (*^^*^^*)

    - $(1,3,4,5,9)$：$1$ 个朝左

    - $(1,2,3,6,9)$：$1$ 个朝右

3. 字符串 ((*^^)

    有两组 $(a,e)$：$(1,6)$、$(2,6)$，每组都能炼 $1$ 个朝右，合计朝右 $2$ 个，朝左 $0$ 个。

（示例仅为其中一种取法，存在其他合法选取方案）

求：能炼制出的**朝左最大总数**、**朝右最大总数**。

输入格式

一行输入字符串 $S$，字符串只包含 ( ^ * )。

输出格式

一行两个整数，空格隔开，先输出朝左数量、再输出朝右数量，末尾换行。

样例

样例 1

(*^^*)

1 1

样例 2

(*^^*^^*)

1 1

样例 3

((*^^)

0 2

样例 4

((^^*))

4 0

数据范围

对于 20% 的数据，$|S| \le 10$。

对于 40% 的数据，$|S| \le 2000$。

对于 100% 的数据，$1\le |S|\le 10000$。

提示

样例输入5：

(*^^)*(^^*)

样例输出 5：

2 2

样例输入 6：

(

样例输出 6：

0 0

样例解释 6：

字符长度不足 个，无法构成五元组。

样例输入 7：

)^^)^^))^*)^^)^(^())^^(*^^)())(*^^)*^*^*)*^^())*((^^^(^^^^^(^^^^^((^^)^(())^**((*(*^((*^)(*^))*(^^^(

样例输出 7：

87 102