После исполнения роли Нео в легендарной трилогии «Матрица», Киану Ривз начал сомневаться: возможно, мы действительно живем в виртуальной реальности? Чтобы это выяснить, ему нужно решить следующую задачу.

Будем называть строку состоящую только из нулей и единиц хорошей, если она содержит различное число нулей и единиц. К примеру, строки 1, 101, 0000 являются хорошими, а 01, 1001 and 111000 не являются хорошими.

Дана строка $$$s$$$ длины $$$n$$$ состоящая только из нулей и единиц. Мы должны разрезать $$$s$$$ на минимально возможное количество подстрок $$$s_1, s_2, \ldots, s_k$$$ таким образом, чтобы все они были хорошими. Более формально, мы должны найти минимальную по количеству строк последовательность хороших строк $$$s_1, s_2, \ldots, s_k$$$ такую, что их конкатенация (последовательное склеивание) равно $$$s$$$, то есть $$$s_1 + s_2 + \dots + s_k = s$$$.

К примеру, разрезания 110010 на 110 и 010 или на 11 и 0010 удовлетворяют условию, так как 110, 010, 11, 0010 являются хорошими, а на меньшее число разрезать 110010 нельзя, так как 110010 хорошей не является. В то же время, разрезание 110010 на 1100 и 10 не удовлетворяет условию, так как обе строки не являются хорошими. Также, разрезание 110010 на 1, 1, 0010 не удовлетворяет условию, так как не является минимальным, хоть все $$$3$$$ строки и являются хорошими.

Можете ли вы помочь Киану? Можно показать, что решение всегда существует. Если существует несколько оптимальных решений, выведите любое из них.