Hide

Problem A
Balance

Languages da en

Decide if a given string of parentheses of two different types is balanced, meaning that the opening and corresponding closing parentheses are properly nested. For instance, “([])()[]” is balanced, but “((” and “)(” and “(]” are not.

To be precise, (i) the empty string is balanced; (ii) if $w$ is balanced then both $(w)$ and $[w]$ are balanced; and (iii) if $w$ and $x$ are balanced then $w x$ is balanced.

Input

The input consists of a single line containing a nonempty sequence $w$ of symbols from the alphabet ${[,], (,)}$ .

Output

Print “1” if $w$ is balanced, “0” if not.

Test groups

Let $| w |$ denote the length of $w$ . In all test groups, we have $1 \leq | w | \leq 200 000$ .

Group	Points	Additional constraints
1	9	There are no “`[`” or “`]`”
2	10	$\| w \| \leq 100$
3	81	None

Sample Input 1	Sample Output 1
([(())])[]	1

Sample Input 2	Sample Output 2
)(	0

Sample Input 3	Sample Output 3
[)	0

Sample Input 4	Sample Output 4
((	0

Sample Input 5	Sample Output 5
[(])	0

Sample Input 6	Sample Output 6
[])[])	0

Sample Input 7	Sample Output 7
(	0

Problem ABalance

Input

Output

Test groups

Problem A
Balance