문제

이 문제는 투 스텝 문제입니다.

( 개와 ) 개로 이루어진 길이 의 괄호 문자열 에 대해, 를 연속으로 개 이어붙인 길이 의 문자열 에서 길이 의 올바른 괄호 부분 문자열을 찾아라.

하지만 당신은 의 절반씩밖에 볼 수 없다. 따라서 당신은 두 단계에 걸쳐 문자열 의 앞 절반과 뒤 절반을 따로 보기로 했다.

첫 번째 단계에서 당신은 에서 첫 번째 괄호부터 번째 괄호까지 개의 괄호를 본 뒤, 를 만족하는 정수 를 두 번째 단계로 전달할 수 있다. 이외의 정보는 전달할 수 없다.

두 번째 단계에서 당신은 에서 앞에서부터 번째 괄호부터 번째 괄호까지 개의 괄호를 본 뒤, 첫 번째 단계에서 당신이 전달한 정수 를 토대로 의 길이 의 올바른 괄호 문자열들 중 하나를 찾아야 한다.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스 코드에 두 단계의 실행 과정을 모두 구현해야 한다.

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 가 주어진다. ()

만약 가 이라면 첫 번째 단계를 수행해야 하고, 가 라면 두 번째 단계를 수행해야 한다.

첫 번째 단계

입력

둘째 줄에 의 절반의 길이 이 주어진다. ()

셋째 줄에 의 첫 글자가 공백 구분 없이 주어진다.

출력

첫째 줄에 두 번째 단계로 전달할 정수 를 출력한다. ()

두 번째 단계

입력

둘째 줄에 과 첫 번째 단계에서 전달한 가 공백으로 구분되어 주어진다. (; )

셋째 줄에 의 마지막 글자가 공백 구분 없이 주어진다.

출력

만약 의 부분 문자열 중 길이 의 올바른 괄호 문자열이 있다면 첫째 줄에 그 부분 문자열의 시작 위치를 출력한다.

만약 그러한 위치가 여러 가지라면 아무 위치나 출력한다.

만약 의 부분 문자열 중 길이 의 올바른 괄호 부분 문자열이 존재하지 않는다면 첫째 줄에 -1을 출력한다.