올바른 괄호 문자열 찾기

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

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

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

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

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

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

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

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