동시에 균형을 이루는 괄호 문자열

길이가 모두 $N$인 괄호 문자열 $K$개가 주어진다 ($1 \le K \le 10$, $1 \le N \le 50000$). 각 문자열을 $S_1, S_2, \dots, S_K$라 하고, 각 문자열의 문자는 $0$번부터 $N-1$번까지 번호가 매겨져 있다.

구간 $i \dots j$ ($0 \le i \le j \le N-1$)가 동시에 균형을 이룬다는 것은, 모든 문자열 $S_1, \dots, S_K$에 대해 위치 $i$부터 $j$까지의 부분 문자열이 각각 균형 잡힌 괄호 문자열임을 뜻한다.

예를 들어 $K = 3$이고 문자열이 다음과 같다고 하자.

S_1 = )()((())))(())
S_2 = ()(()()()((())
S_3 = )))(()()))(())
                1111
      01234567890123

이때 구간 $3 \dots 8$은 동시에 균형을 이룬다. $S_1[3\dots8] = ((()))$, $S_2[3\dots8] = ()()()$, $S_3[3\dots8] = (()())$가 모두 균형 잡힌 문자열이기 때문이다. 구간 $10 \dots 13$과 $11 \dots 12$ 역시 동시에 균형을 이룬다.

구간 $i \dots j$가 동시에 균형을 이루는 쌍 $(i, j)$의 개수를 세어라.

괄호 문자열이 균형 잡혀 있다는 것은, (와 )의 개수가 같고 모든 접두사에서 (의 개수가 )의 개수 이상임을 뜻한다. 예를 들어 다음 문자열들은 균형 잡혀 있다.

• ()
• (())
• ()(()())

반면 다음 문자열들은 그렇지 않다.

• )(
• ())(
• ((())))

• 첫째 줄: 두 정수 $K$와 $N$.
• 둘째 줄부터 $K+1$번째 줄까지: 각 줄에 길이 $N$인 괄호 문자열이 하나씩 주어진다.

• 동시에 균형을 이루는 구간 $(i, j)$의 개수를 정수 하나로 출력한다.