A bracket sequence is a string containing only characters "(" and ")".

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You are given $\mathrm{nn\; bracket\; sequences\; s1,s2,\dots ,sns1,s2,\dots ,sn\; .\; Calculate\; the\; number\; of\; pairs\; i,j(1\le i,j\le n)i,j(1\le i,j\le n)\; such\; that\; the\; bracket\; sequence\; si+sjsi+sj\; is\; a\; regular\; bracket\; sequence.\; Operation\; ++\; means\; concatenation\; i.e.\; "()("\; +\; ")()"\; =\; "()()()".}$

If ${\mathrm{si+sjsi+sj\; and\; sj+sisj+si\; are\; regular\; bracket\; sequences\; and\; i\ne ji\ne j\; ,\; then\; both\; pairs\; (i,j)(i,j)\; and\; (j,i)(j,i)\; must\; be\; counted\; in\; the\; answer.\; Also,\; if\; si+sisi+si\; is\; a\; regular\; bracket\; sequence,\; the\; pair\; (i,i)(i,i)\; must\; be\; counted\; in\; the\; answer.}}^{}$

Input

The first line contains one integer $\mathrm{n(1\le n\le 3\cdot 105)n(1\le n\le 3\cdot 105)\; —\; the\; number\; of\; bracket\; sequences.\; The\; following\; nn\; lines\; contain\; bracket\; sequences\; —\; non-empty\; strings\; consisting\; only\; of\; characters\; "("\; and\; ")".\; The\; sum\; of\; lengths\; of\; all\; bracket\; sequences\; does\; not\; exceed\; 3\cdot 1053\cdot 105\; .}$

Output

In the single line print a single integer — the number of pairs $\mathrm{i,j(1\le i,j\le n)i,j(1\le i,j\le n)\; such\; that\; the\; bracket\; sequence\; si+sjsi+sj\; is\; a\; regular\; bracket\; sequence.}$

Examples

Input

3 ) () (

Output

 

2

Input

 

2 () ()

Output

4

Note

In the first example, suitable pairs are $(3,1)(3,1)\; and\; (2,2)(2,2)\; .$

In the second example, any pair is suitable, namely $(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)\; .$

题意：有n个字符串，每个字符串都只有'('和')'组成，从中找出两个字符串可以构成完全匹配的个数(这两个字符串也可以由自己本身组成，如(2,2),(1,1).

题解：所有的字符串可以分为3类:1.自身完美匹配型（即左括号和右括号完美匹配）2：除去完全匹配的子串，剩下的都是左括号，3：除去完全匹配的子串，剩下的都是右括号。对于第一类他的个数ans=c(n,2)*A(2,2)+n(它自身构成的完美匹配），对于第二类和第3类，用map查询一遍（如果有左括号的个数等于右括号的个数，ans=(左括号的种类*右括号的种类），最后不要忘记除去2，因为我们算了两遍。还有一点要注意的是一定要用long long ，我错了好几次才发现这一点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include