import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; public class Main { static StringBuilder out = new StringBuilder(); static boolean[] dig, searchedNum; static int len, n, maxBitsLen; static int[] canPutNum, bitlen; static int[][] order; static Map getOrder = new HashMap<>(); static List> numInd = new ArrayList<>(); static List> indNum = new ArrayList<>(); static boolean[] stopFlag; public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); /* * DFSを枝刈りして解く */ //入力を桁ごとにboolで受け取る { char[] c = sc.next().toCharArray(); len = c.length; //最後に番兵をつける dig = new boolean[len+1]; dig[len] = true; for(int i = 0; i < len; i++) { dig[i] = c[i] == '1'; } } // n =順列の最大値+1 { int cnt = 0; for(n = 1; cnt < len; n++) { int ii = n; while(ii > 0) { ii >>= 1; cnt++; } } } //入力のbit列に置ける位置 canPutNum = new int[n]; for(int i = 0; i < n; i++) numInd.add(new HashSet<>()); for(int i = 0; i < len; i++) indNum.add(new ArrayList<>()); for(int l = 0; l < len; l++){ if(!dig[l]) continue; int tmp = 0; for(int r = l; r < len; r++) { tmp <<= 1; if(dig[r]) tmp++; if(tmp >= n) break; if(!dig[r+1]) continue; numInd.get(tmp).add(l); indNum.get(l).add(tmp); canPutNum[tmp]++; } } //探索する優先順位 order = new int[n-1][3]; bitlen = new int[n]; for(int i = 0; i+1 < n; i++) { int ConsecutiveZeros = 0; int cost = 0; int ii = i+1; while(ii > 0) { if((1&ii) == 1) { cost += ConsecutiveZeros*ConsecutiveZeros; ConsecutiveZeros = 0; }else { ConsecutiveZeros++; } bitlen[i+1]++; ii >>= 1; } maxBitsLen = bitlen[n-1]; order[i][0] = i+1; order[i][1] = cost; order[i][2] = canPutNum[i+1]; } /* * inputのbit列に出現数が少ない->costが大きい->数が大きい * 順で探索する * costはbit表記の時に連続した0の数を2乗した和 * * costが同じなら値が大きいものを優先することで * 内包されている関係を一方向だけで考えられる * 13(1101)と5(101)の時、costはどちらも同じになり * 上記条件により13が先に探索される */ Arrays.sort(order, (x, y) -> Integer.compare(y[0], x[0])); Arrays.sort(order, (x, y) -> Integer.compare(y[1], x[1])); Arrays.sort(order, (x, y) -> Integer.compare(x[2], y[2])); for(int i = 0; i+1 < n; i++) getOrder.put(order[i][0], i); stopFlag = new boolean[len]; searchedNum = new boolean[n]; if(!dfs(0)) { System.out.println(-1); return; } //order[i][1]にはその数字を置いた //indが入っているため降順でansになる Arrays.sort(order, (x, y) -> Integer.compare(x[1], y[1])); //答えからbitsを生成 // for(int i = 0; i < order.length; i++) { // String tmp = ""; // int ii = order[i][0]; // while(ii > 0) { // if((1&ii) == 1) // tmp = '1' + tmp; // else // tmp = '0' + tmp; // // ii >>= 1; // } // out.append(tmp); // } // // out.append("\n"); for(int i = 0; i < order.length; i++) { out.append(order[i][0]); out.append(' '); } System.out.println(out); } private static boolean dfs(int depth) { if(depth == order.length) { return true; } int p = order[depth][0]; //interrupt済なら飛ばす if(searchedNum[p]) if(dfs(depth+1)) return true; ArrayList indexList = new ArrayList<>(numInd.get(p)); List removeList = new ArrayList<>(); List interruptList = new ArrayList<>(); for(int l : indexList) { int r = l+bitlen[p]-1; boolean f = true; int lowerLim = 0; for(int ll = l-1; ll+maxBitsLen > l; ll--) { if(ll < 0) break; lowerLim <<= 1; lowerLim++; if(!dig[ll]) continue; if(stopFlag[ll]) break; int removeInd = getUpperBound(lowerLim, indNum.get(ll)); int arrSize = indNum.get(ll).size(); for(; removeInd < arrSize; removeInd++) { int remove = indNum.get(ll).get(removeInd); if(numInd.get(remove).remove(ll)) { removeList.add(new Pair(remove, ll)); canPutNum[remove]--; if(canPutNum[remove] == 0) { f = false; break; }else if(canPutNum[remove] == 1 && !searchedNum[remove]) { //canPutNumが1で未探索なら位置が確定しているので先に探索する int interruptInd = new ArrayList<>(numInd.get(remove)).get(0); if(!interrupt(remove, interruptInd, removeList, interruptList)) { f = false; break; } order[getOrder.get(remove)][1] = interruptInd; searchedNum[remove] = true; interruptList.add(remove); } } } if(!f) break; } if(f)for(int ll = l; ll <= r; ll++) { for(int remove : indNum.get(ll)) { if(remove == p) continue; if(numInd.get(remove).remove(ll)) { removeList.add(new Pair(remove, ll)); canPutNum[remove]--; if(canPutNum[remove] == 0) { f = false; break; }else if(canPutNum[remove] == 1 && !searchedNum[remove]) { int interruptInd = new ArrayList<>(numInd.get(remove)).get(0); if(!interrupt(remove, interruptInd, removeList, interruptList)) { f = false; break; } order[getOrder.get(remove)][1] = interruptInd; searchedNum[remove] = true; interruptList.add(remove); } } } } if(f) { stopFlag[l] = true; stopFlag[r] = true; searchedNum[p] = true; order[depth][1] = l; if(dfs(depth+1)) return true; searchedNum[p] = false; stopFlag[l] = false; stopFlag[r] = false; } for(Pair pair : removeList) { if(!numInd.get(pair.a).contains(pair.b)) { numInd.get(pair.a).add(pair.b); canPutNum[pair.a]++; } } for(int interrupt : interruptList) searchedNum[interrupt] = false; } return false; } private static boolean interrupt(int p, int l, List removeList, List interruptList) { int r = l+bitlen[p]-1; boolean f = true; int lowerLim = 0; for(int ll = l-1; ll+maxBitsLen > l; ll--) { if(ll < 0) break; lowerLim <<= 1; lowerLim++; if(!dig[ll]) continue; if(stopFlag[ll]) break; int removeInd = getUpperBound(lowerLim, indNum.get(ll)); int arrSize = indNum.get(ll).size(); for(; removeInd < arrSize; removeInd++) { int remove = indNum.get(ll).get(removeInd); if(numInd.get(remove).remove(ll)) { removeList.add(new Pair(remove, ll)); canPutNum[remove]--; if(canPutNum[remove] == 0) { f = false; break; }else if(canPutNum[remove] == 1 && !searchedNum[remove]) { int interruptInd = new ArrayList<>(numInd.get(remove)).get(0); if(!interrupt(remove, interruptInd, removeList, interruptList)) { f = false; break; } order[getOrder.get(remove)][1] = interruptInd; searchedNum[remove] = true; interruptList.add(remove); } } } if(!f) break; } if(f)for(int ll = l; ll <= r; ll++) { for(int remove : indNum.get(ll)) { if(remove == p) continue; if(numInd.get(remove).remove(ll)) { removeList.add(new Pair(remove, ll)); canPutNum[remove]--; if(canPutNum[remove] == 0) { f = false; break; }else if(canPutNum[remove] == 1 && !searchedNum[remove]) { int interruptInd = new ArrayList<>(numInd.get(remove)).get(0); if(!interrupt(remove, interruptInd, removeList, interruptList)) { f = false; break; } order[getOrder.get(remove)][1] = interruptInd; searchedNum[remove] = true; interruptList.add(remove); } } } } return f; } private static int getUpperBound(int lowerLim, List arr) { int l = 0; int r = arr.size()-1; while(l <= r) { int m = (l+r)/2; if(arr.get(m) <= lowerLim) l = m+1; else r = m-1; } return l; } } class Pair{ int a, b; Pair(int a, int b){ this.a = a; this.b = b; } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public FastScanner(InputStream in2) { // TODO 自動生成されたコンストラクター・スタブ } private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} }