Рассмотрим следующий код сортировки слиянием на языке 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$$$) — элементы перестановки.

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

Сортировка слиянием

Examples