33903번 - 괄호 붙이기

문제

올바른 괄호 문자열은 다음과 같이 정의한다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다.
3. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다.

예를 들어, ()(), (()), (((()))(())) 등은 올바른 괄호 문자열이고, (((), )(, )))()()(( 등은 그렇지 않다.

(, )로 이루어진 문자열 $A,ドル $B$가 주어진다.

$A$를 길이 1ドル$ 이상의 연속된 두 문자열 $A_1,ドル $A_2$로 순서를 유지해서 나눈 후 $A_1,ドル $B,ドル $A_2$를 이어붙여 새롭게 $A_1+B+A_2$라는 문자열을 만들었을 때,

올바른 괄호 문자열이 되도록 $A_1,ドル $A_2$를 나눌 수 있다면 1ドル,ドル 아니면 0ドル$을 출력한다.

입력

첫 번째 줄과 두 번째 줄에 괄호로 이루어진 문자열 $A,ドル $B$가 주어진다. $(2 \le |A| \le 200,000円;$ 1ドル \le |B| \le 200,000円)$

출력

$A_1+B+A_2$가 올바른 괄호 문자열이 되도록 $A$를 나누는 방법이 존재하면 1ドル,ドル 아니면 0ドル$을 출력한다.

제한

힌트