천문대의 중첩 작업 로그

문제

천문대의 운영 서버는 관측 장비가 수행한 작업을 하나의 문자열로 저장한다. 담당자는 이 로그에서 오류가 많이 발생한 작업을 찾아 운영 보고서에 기록하려고 한다. 하나의 작업 안에서 보조 작업이 실행될 수 있으므로 로그에는 여러 단계로 중첩된 작업이 나타날 수 있다. 로그에 사용하는 문자는 여는 괄호 '(', 닫는 괄호 ')', 마침표 '.', 느낌표 '!'의 네 종류다. 여는 괄호는 새 작업의 시작을 나타내고, 그와 짝을 이루는 닫는 괄호는 해당 작업의 종료를 나타낸다. 마침표는 정상 처리 사건 하나를, 느낌표는 오류 사건 하나를 나타낸다. 작업은 시작한 순서의 역순으로 종료된다. 모든 괄호는 올바르게 짝을 이루며, 정상 처리와 오류 사건은 반드시 하나 이상의 작업이 실행 중일 때만 나타난다. 아무 사건도 없는 작업도 허용한다. 어떤 작업의 오류 수는 그 작업의 여는 괄호와 닫는 괄호 사이에 있는 느낌표의 개수다. 보조 작업에서 발생한 오류도 바깥 작업의 오류 수에 포함한다. 따라서 하나의 오류 사건이 여러 작업의 오류 수에 함께 포함될 수 있다. 서로 중첩되지 않은 별개의 작업이 연달아 기록될 수도 있다. 보고 대상은 오류 수가 정수 K 이상인 작업이다. 서버는 보고 대상 작업의 개수, 보고 대상 중 가장 큰 오류 수, 그리고 그 최댓값을 가진 작업의 시작 위치를 출력해야 한다. 시작 위치는 전체 로그 문자열에서 여는 괄호가 등장한 위치이며 첫 문자의 위치는 1이다. 최대 오류 수가 같은 작업이 여러 개라면 시작 위치가 가장 작은 작업을 선택한다. 보고 대상이 하나도 없으면 세 값 모두 0으로 기록한다. 로그를 분석하여 이 보고 내용을 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 2 ≤ N ≤ 200,000, 1 ≤ K ≤ N이다.
둘째 줄에 길이가 정확히 N인 로그 문자열이 주어진다. 문자열은 '(', ')', '.', '!'로만 이루어지며 공백은 없다. 괄호는 올바르게 짝을 이루고, '.'와 '!'는 반드시 하나 이상의 괄호 쌍 내부에 있다. 작업은 적어도 하나 존재한다.

출력

보고 대상 작업의 개수, 보고 대상의 최대 오류 수, 동점 규칙에 따라 선택한 작업의 시작 위치를 공백으로 구분하여 출력한다. 보고 대상이 없으면 0 0 0을 출력한다.

11 2
(.(!!).(!))

2 3 1

7 1
(()(.))

0 0 0

8 1
(!)(.!!)

2 2 4

출처: Devin.KR 자체 제작