동시에 균형 잡힌 문자열

실행 시간 제한	메모리 제한
1 초	128 MB

수진의 고양이들은 모두 특이한 종으로서 각자 외모가 독특하다.

각 고양이는 괄호 모양의 거대한 반점으로 표시되어 있다. (바라보는 방향에 따라 왼쪽 또는 오른쪽 괄호처럼 보일 수 있음)

어느 날 아침, 수진은 고양이들을 K 줄로 배열했으며, 각 줄에는 N마리의 고양이들이 서있다(1 <= K <=10, 1 <= N <= 50,000).

고양이들은 각자 임의의 방향을 바라보고 있기 때문에, 이 줄 세우기는 괄호의 K길이-N 문자열 S_1, ..., S_k로 설명할 수 있다.

수진은 몇몇 범위의 고양이들이 '동시에 균형잡혀'있다는 것을 확인했다.

i...j 범위의 소들이 '동시에 균형잡혀'있다는 것은 S_1, ..., S_k의 문자열이 그 범위에서 균형을 이루고 있을 때만 해당된다(아래에서 괄호의 문자열이 균형을 이루는 것이 무슨 의미인지 정의한다).

예를 들어, K = 3인 경우,

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

이 경우 범위 [3...8]은 동시에 균형잡혀 있다. 왜냐하면 S_1[3...8] = ((())), S_2[3...8] = ()()(), 그리고 S_3[3...8] = (()()). 범위 [10...13]과 [11...12]도 동시에 균형을 이루고 있다.

여러분은 괄호의 K길이-N 문자열이 주어질 때, 수진이 i...j 범위가 동시에 균형잡혀 있는 (i,j) 쌍의 수를 세는 것을 도와주어야한다.

괄호의 한 문자열이 '균형을 이루고 있다'는 것에 대해서는 여러 가지 방법으로 정의할 수 있는데, 가장 간단한 정의는 '('와 ')'의 총 개수가 같아야 하며, 문자열의 어떤 접두사에서도 '('의 개수가 ')'의 개수보다 많거나 같아야 한다는 것이다.

예를 들어, 다음 문자열들은 모두 균형을 이루고 있다:

아래의 예시은 균형을 이루고 있지 않다:

3 14
)()((())))(())
()(()()()((())
)))(()()))(())