Statement is not available on English language
E2. Сортировка слиянием
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующий код сортировки слиянием на языке Python:

def sort(a):
n = len(a)
b = [0 for i in range(n)]
log = []

def mergeSort(l, r):
if r - l <= 1:
return
m = (l + r) >> 1
mergeSort(l, m)
mergeSort(m, r)
i, j, k = l, m, l
while i < m and j < r:
if a[i] < a[j]:
log.append('0')
b[k] = a[i]
i += 1
else:
log.append('1')
b[k] = a[j]
j += 1
k += 1
while i < m:
b[k] = a[i]
i += 1
k += 1
while j < r:
b[k] = a[j]
j += 1
k += 1
for p in range(l, r):
a[p] = b[p]

mergeSort(0, n)
return "".join(log)

Как можно заметить, этот код использует логирование — важнейший инструмент разработки.

Старший разработчик ВКонтакте Вася сгенерировал перестановку $$$a$$$ (массив из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$), дал её на вход функции sort и получил на выходе строку $$$s$$$. На следующий день строку $$$s$$$ Вася нашёл, а перестановка $$$a$$$ потерялась.

Вася хочет восстановить любую перестановку $$$a$$$ такую, что вызов функции sort от неё даст ту же строку $$$s$$$. Помогите ему!

Входные данные

Ввод содержит непустую строку $$$s$$$, состоящую из символов 0 и 1.

В этой версии задачи для любого теста существует перестановка длины не более $$$10^3$$$, удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе превышающую $$$10^3$$$.

Выходные данные

В первой строке выведите целое число $$$n$$$ — длину перестановки.

Во второй строке выведите $$$n$$$ различных целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Если существует несколько вариантов ответа, выведите любой из них.

Примеры
Входные данные
00000000000000000000000000000000
Выходные данные
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Входные данные
11111111111111111111111111111111
Выходные данные
16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Входные данные
101011010001100100011011001111011000011110010
Выходные данные
16
13 6 1 7 12 5 4 15 14 16 10 11 3 8 9 2