После исполнения роли Нео в легендарной трилогии «Матрица», Киану Ривз начал сомневаться: возможно, мы действительно живем в виртуальной реальности? Чтобы это выяснить, ему нужно решить следующую задачу.
Будем называть строку состоящую только из нулей и единиц хорошей, если она содержит различное число нулей и единиц. К примеру, строки 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\) строки и являются хорошими.
Можете ли вы помочь Киану? Можно показать, что решение всегда существует. Если существует несколько оптимальных решений, выведите любое из них.
Выходные данные
В первой строке выведите одно целое число \(k\) (\(1\le k\)) — искомое минимальное количество частей, на которое нужно разрезать \(s\).
Во второй строке через пробел выведите \(k\) строк \(s_1, s_2, \ldots, s_k\). Длина каждой строки должна быть положительной. Их конкатенация (последовательное склеивание) должна равняться \(s\), и все они должны быть хорошими.
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере, строка 1 вообще не была разрезана. Она является хорошей, поэтому условие выполнено.
Во втором примере, 1 and 0 обе являются хорошими. Строка 10 хорошей не является, поэтому ответ действительно минимальный.
В третьем примере, 100 и 011 обе являются хорошими. Строка 100011 хорошей не является, поэтому ответ действительно минимальный.