괄호 트리

뿌리가 있는 순서 트리 $T$는 짝이 맞는 괄호 문자열 $p(T)$로 나타낼 수 있다. 노드가 하나뿐인 트리는 ()로 나타낸다. 루트가 순서가 정해진 부분트리 $T\_1, T\_2, \dots , T\_k$ 를 자식으로 $k$개 가지면, $p(T)$는 다음과 같이 정의한다.

$p(T) ≔$ ( $+ p(T\_1) + p(T\_2) + \cdots + p(T\_k) +$ )

여기서 $+$는 문자열 연결을 뜻한다. 아래 그림은 뿌리 있는 순서 트리 두 개를 보여준다. 트리 $T\_L$과 $T\_R$의 문자열 표현 $p(T\_L)$과 $p(T\_R)$은 각각 ((()()())())와 (()((()(()))()))이다.

뿌리에서 잎 노드까지의 거리는 뿌리에서 그 잎까지 가는 동안 지나는 간선의 개수이다. 그림에서 뿌리 노드는 파란색이고, 뿌리에서 각 잎까지의 거리가 표시되어 있다. 뿌리에서 모든 잎까지 거리의 합은 $T\_L$이 $7$, $T\_R$이 $10$이다.

하나의 뿌리 있는 순서 트리만을 나타내는 짝이 맞는 괄호 문자열이 주어진다. 뿌리에서 모든 잎 노드까지 거리의 합을 구하는 프로그램을 작성하라.

한 줄에 하나의 뿌리 있는 순서 트리를 나타내는 짝이 맞는 괄호 문자열이 주어진다. 문자열에는 괄호 이외의 문자가 없다. 문자열의 길이는 2 이상 $10^7$ 이하이다.

트리의 뿌리에서 모든 잎 노드까지 거리의 합을 한 줄에 출력한다.