Олег ведёт историю прожитых им дней, отмечая в ней каждый день либо как хороший, либо как плохой. Олег называет зеброй непустую последовательность дней, начинающуюся и заканчивающуюся плохим днём, в которой хорошие и плохие дни чередуются. Будем обозначать плохие дни за 0, а хорошие за 1. Тогда, например, последовательности дней 0, 010, 01010 являются зебрами, а последовательности 1, 0110 и 0101 не являются.

Олег сообщил вам историю прожитых им дней в хронологическом порядке в виде строки из символов 0 и 1, и теперь вас интересует, можно ли разбить историю Олега на несколько подпоследовательностей, каждая из которых является зеброй, и, если да, то как это можно сделать. Каждый день должен попасть ровно в одну подпоследовательность. Дни в каждой подпоследовательности должны следовать в хронологическом порядке. Обратите внимание, что подпоследовательность не обязана образовывать группу подряд идущих дней.