Строка называется скобочной последовательностью, если в ней нет символов, отличных от «(» и «)». Скобочная последовательность называется правильной, если можно получить из нее корректное математическое выражение путем вставки в нее символов «+» и «1». Например, «», «(())» и «()()» — правильные скобочные последовательности; «))» и «)((» — скобочные последовательности, не являющиеся правильными, а «(a)» и «(1)+(1)» — не скобочные последовательности.
У вас есть несколько строк, каждая строка является скобочной последовательностью длины \(2\). Всего у вас \(cnt_1\) строк «((», \(cnt_2\) строк «()», \(cnt_3\) строк «)(» и \(cnt_4\) строк «))». Вы хотите записать эти строки в некотором порядке друг за другом; после этого у вас получится длинная скобочная последовательность из \(2(cnt_1 + cnt_2 + cnt_3 + cnt_4)\) символов. Вам необходимо ответить на следующий вопрос: можно ли выбрать некоторый порядок строк, что в итоге получится правильная скобочная последовательность? Обратите внимание: нельзя ни удалять, ни добавлять новые символы или строки.
Выходные данные
Выведите одно целое число: \(1\), если можно выбрать некоторый порядок строк и записать их друг за другом, в результате чего получится правильная скобочная последовательность; \(0\), если это невозможно.
Примечание
В первом примере можно построить строку «(())()(()((()()()())))», которая является правильной скобочной последовательностью.
Во втором примере можно построить строку «», которая является правильной скобочной последовательностью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
4
3
|
1
|
|
2
|
0
0
0
0
|
1
|
|
3
|
1
2
3
4
|
0
|