34839번 - 올바른 괄호 문자열 찾기 투 스텝

문제

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

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

하지만 이 문제는 투 스텝 문제이기 때문에 당신은 두 단계에 걸쳐 문자열 $S$의 앞 절반과 뒤 절반을 따로 보아야 한다.

첫 번째 단계에서 당신은 $S$에서 첫 번째 괄호부터 $N$번째 괄호까지 $N$개의 괄호를 본 뒤, 0ドル\le w\le 2^{20}-1$를 만족하는 정수 $w$를 두 번째 단계로 전달할 수 있다. $w$ 이외의 정보는 전달할 수 없다.

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

입력

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

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 $t$가 주어진다. (1ドル \leq t \leq 2$)

만약 $t$가 1ドル$이라면 첫 번째 단계를 수행해야 하고, $t$가 2ドル$라면 두 번째 단계를 수행해야 한다.

출력

제한

첫 번째 단계

입력

둘째 줄에 $S$의 절반의 길이 $N$이 주어진다. (1ドル \leq N \leq 1,000円$)

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

출력

첫째 줄에 두 번째 단계로 전달할 정수 $w$를 출력한다. (0ドル \leq w \leq 2^{20}-1$)

두 번째 단계

입력

둘째 줄에 $N$과 첫 번째 단계에서 전달한 $w$가 공백으로 구분되어 주어진다. (1ドル \leq N \leq 1,000円$; 0ドル \le w \le 2^{20}-1$)

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

출력

만약 $T$의 부분 문자열 중 길이 2ドルN$의 올바른 괄호 부분 문자열이 있다면 첫째 줄에 그 부분 문자열의 시작 위치를 출력한다. 첫 번째 문자의 위치는 1ドル$이다.

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

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

노트