3. Гирлянды из чисел

Чем украшают ёлочку программисты? Гирляндами из единичек и ноликов. Обязательно чётной длины (а иначе некрасиво). А когда новогодние праздники заканчиваются (потому что подступают майские) ёлочку приходится разбирать, демонтировать пыльные гирлянды…

— А давайте сыграем! – предложил молодой программист Даня. – Берём гирлянду и по очереди отрываем от неё цифры, можно справа, можно слева, но ровно одну за ход. У кого сумма получится меньше – тот проиграл и идёт выносить ёлку на помойку. Вы, сэнсэй, естественно, ходите первым. Согласны?

— Согласен, — произнёс сэнсэй, а пальцы его продолжали танцевать на клавиатуре. — Только за меня будет играть программа. Она будет выбирать, откуда отрывать очередную цифру, слева или справа.

— А как она ёлку будет выносить, если проиграет?

— Она не проиграет. Хотя в некоторых случаях может приключиться ничья. А во всех остальных случаях у программы есть выигрышная стратегия.

Даня вздохнул, обнял ёлку и удалился с ней. Он знал, что сэнсей всегда прав.

Вам не придётся воспроизводить всю программу сэнсэя. Достаточно написать программу, делающую первый ход.

Входные данные. Строка из 0 и 1 длиной до 1000 символов, причём эта длина чётная.

Выходные данные. -1, если для выигрыша нужно на первом ходу откусить цифру слева, 1, если справа, и 0, если при любом первом ходе и безошибочной игре соперника будет ничья.