import java.io.IOException; import java.io.InputStream; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Queue; public class Main { static final int inf = Integer.MAX_VALUE / 2; static StringBuilder out = new StringBuilder(); static boolean[] dig; static int n, ln; static int[] imos; static int[][] order; static Map zeromap = new HashMap<>(); static List> index = new ArrayList<>(); static SegmentTree st; public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); /* * 枝刈り法をベースに解く * 0の位置をもとに0の多い数から順列に当てはめていく * その位置のbitをまだ使ってないかは区間和のセグ木で判定する * その区間の和が0ならまだ使ってないので使い、区間の値を全て1にする。 */ //入力を桁ごとにboolで受け取る { char[] c = sc.next().toCharArray(); n = c.length; //最後に番兵をつける dig = new boolean[n+1]; dig[n] = true; imos = new int[n+1]; for(int i = 0; i < n; i++) { dig[i] = c[i] == '1'; imos[i+1] = imos[i] + (dig[i] ? 1 : 0); } } // ln =順列の最大値+1 { int cnt = 0; for(ln = 1; cnt < n; ln++) { int ii = ln; while(ii > 0) { ii >>= 1; cnt++; } } } //探索する優先順位 order = new int[ln-1][3]; for(int i = 0; i+1 < ln; i++) { int maxConsecutiveZeros = 0; int ConsecutiveZeros = 0; int cntZeros = 0; int ii = i+1; while(ii > 0) { if((1&ii) == 1) { maxConsecutiveZeros = Math.max(ConsecutiveZeros, maxConsecutiveZeros); ConsecutiveZeros = 0; }else { ConsecutiveZeros++; cntZeros++; } ii >>= 1; } order[i][0] = i+1; order[i][1] = cntZeros; order[i][2] = maxConsecutiveZeros; } //連続した0の数が多いほど優先する //それが同じなら0の数が多いほど優先する //それも同じならその数の大きい順 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(y[2], x[2])); //すべての0始まり0終わりのパターン(正規表現で'(0+1+)*0+')を抽出し、連続した値に変換するmapを作る int mapsize = 0; { for(int i = 1; i < ln; i++){ int ii = i; while((1&ii) == 1) ii >>= 1; if(ii == 0) continue; long key = 0; int cntz = 0; int cnto = 0; while((1 & ii) == 0){ ii >>= 1; key++; } while((1 & ii) == 1){ ii >>= 1; cnto++; } long v = 16; while(ii > 0){ while((1 & ii) == 0){ ii >>= 1; cntz++; } key += cnto*v; v <<= 4; key += cntz*v; v <<= 4; cntz = 0; cnto = 0; while((1 & ii) == 1){ ii >>= 1; cnto++; } } if(!zeromap.containsKey(key)) zeromap.put(key, mapsize++); } } // System.out.println("zeromap : "); // for(long key : zeromap.keySet()) { // // Deque kl = new ArrayDeque<>(); // String rekey = key + "(1"; // // long tkey = key; // while(tkey > 0) { // kl.push((int)(tkey%16)); // tkey /= 16; // } // // boolean odd = false; // while(!kl.isEmpty()) { // int tmp = kl.pollFirst(); // for(int i = 0; i < tmp; i++) // rekey += odd ? '1' : '0'; // // odd = !odd; // } // // rekey += ") -> " + zeromap.get(key); // // System.out.println(rekey); // } // System.out.println(""); //入力に出てくる //直前に1のある0から始まり、直後に1のある0で終わるパターン //(正規表現で'10+(1+0*)*1')の位置を記録 for(int i = 0; i < mapsize; i++) index.add(new ArrayDeque<>()); for(int l = 1; l < n; l++){ if(dig[l-1] != true || dig[l] != false) continue; long key = 0; boolean prev = false; int cntz = 0; int cnto = 0; long now = 1; for(int r = l; r < n; r++){ now <<= 1; if(dig[r]) now++; if(now >= ln) break; if(prev != dig[r]) { if(dig[r]) cnto = 0; else cntz = 0; prev = dig[r]; } if(dig[r]){ cnto++; }else{ cntz++; if(dig[r+1] == true) { key <<= 4; key += cnto; key <<= 4; key += cntz; index.get(zeromap.get(key)).add(l); } } } } // System.out.println("index:"); // for(int i = 0; i < index.size(); i++) { // String str = "" + i + " ->"; // int qs = index.get(i).size(); // for(int j = 0; j < qs; j++) { // int t = index.get(i).poll(); // str += " " + t; // index.get(i).add(t); // } // System.out.println(str); // } // System.out.println(""); st = new SegmentTree(n); if(!dfs(0)) { System.out.println(-1); return; } for(int i = 0; i < n; i++) { st.getsum(i, i+1); } Arrays.sort(order, (x, y) -> Integer.compare(x[1], y[1])); String ans = ""; String anss = ""; int indcnt = 0; for(int i = 0; i < order.length; i++) { out.append(order[i][0] + " "); String an = ""; int tmp = order[i][0]; int cnt = 0; while(tmp > 0) { if((1&tmp) == 1) an = '1' + an; else an = '0' + an; tmp >>= 1; cnt++; } anss += an; an = "(" + order[i][0] + ":" + indcnt + ")" + an; indcnt += cnt; ans += an; } // System.out.println(anss); // System.out.println(ans); System.out.println(out); } private static boolean dfs(int ind) { if(ind == order.length) { return true; } long key = 0; int lo = 0; int bitSize = 0; int bitCount = 0; int p = order[ind][0]; while((1&p) == 1) { p >>= 1; bitSize++; bitCount++; } if(p > 0) { int cntz = 0; int cnto = 0; while((1 & p) == 0){ p >>= 1; bitSize++; key++; } while((1 & p) == 1){ p >>= 1; bitSize++; bitCount++; cnto++; lo++; } long v = 16; while(p > 0){ while((1 & p) == 0){ p >>= 1; bitSize++; cntz++; } key += cnto*v; v <<= 4; key += cntz*v; v <<= 4; cntz = 0; cnto = 0; lo = 0; while((1 & p) == 1){ p >>= 1; bitSize++; bitCount++; cnto++; lo++; } } } // String str = order[ind][0] + "(" + Integer.toString(order[ind][0], 2) + ") key=" + key; // System.out.println(str); //二進数表記で0が含まれていない場合 if(key == 0) { for(int i = 0; i < n; i++) { if(i+bitSize > n) continue; if(!dig[i+bitSize]) continue; if(imos[i+bitSize] - imos[i] != bitSize) continue; if(st.getsum(i, i+bitSize) == 0) { st.set(i, i+bitSize, 1); order[ind][1] = i; if(dfs(ind+1)) return true; st.set(i, i+bitSize, 0); } } }else { int inkey = zeromap.get(key); int qsize = index.get(inkey).size(); for(int i = 0; i < qsize; i++) { int tmp = index.get(inkey).poll(); int l = tmp-lo; int r = l+bitSize-1; if(l >= 0 && r < n) if(dig[r+1]) if(imos[r+1] - imos[l] == bitCount) if(st.getsum(l, r+1) == 0) { st.set(l, r+1, 1); order[ind][1] = l; if(dfs(ind+1)) return true; st.set(l, r+1, 0); } index.get(inkey).add(tmp); } } return false; } } class SegmentTree { private int n; int[] node; SegmentTree(int size){ n = 1; while(n < size) n *= 2; node = new int[2*n-1]; } void set(int a, int b, int x){ set(a, b, x, 0, 0, -1); } private void set(int a, int b, int x, int k, int l, int r) { if(r < 0) r = n; if(b <= l || r <= a) return; if(l+1 == r) { node[k] = x; }else { set(a, b, x, 2*k+1, l, (l+r)/2); set(a, b, x, 2*k+2, (l+r)/2, r); node[k] = node[2*k+1] + node[2*k+2]; } } int getsum(int a, int b) { return getsum(a, b, 0, 0, -1); } private int getsum(int a, int b, int k, int l, int r) { if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = getsum(a, b, 2*k+1, l, (l+r)/2); int vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } } //class SegmentTree { // private int n; // int[] node, lazy; // int inf = Integer.MAX_VALUE/2; // // // SegmentTree(int size){ // n = 1; // while(n < size) // n *= 2; // // node = new int[n*2-1]; // lazy = new int[n*2-1]; // // Arrays.fill(lazy, inf); // } // // private void eval(int k, int l, int r) { // if(lazy[k] != inf) { // node[k] = lazy[k]; // // if(l+1 < r) { // lazy[2*k+1] += lazy[k] /2; // lazy[2*k+2] += lazy[k] /2; // } // // lazy[k] = inf; // } // } // // void set(int a, int b, int x) { // set(a, b, x, 0, 0, -1); // } // private void set(int a, int b, int x, int k, int l, int r) { // if(r < 0) // r = n; // // eval(k, l, r); // // if(b <= l || r <= a) // return; // // if(a <= l && r <= b) { // lazy[k] = (r-l)*x; // eval(k, l, r); // }else { // set(a, b, x, 2*k+1, l, (l+r)/2); // set(a, b, x, 2*k+2, (l+r)/2, r); // node[k] = node[2*k+1] + node[2*k+2]; // } // // // } // // int getsum(int a, int b) { // return getsum(a, b, 0, 0, -1); // } // private int getsum(int a, int b, int k, int l, int r) { // if(r < 0) // r = n; // if(b <= l || r <= a) // return 0; // // eval(k, l, r); // if(a <= l && r <= b) // return node[k]; // // int vl = getsum(a, b, 2*k+1, l, (l+r)/2); // int vr = getsum(a, b, 2*k+2, (l+r)/2, r); // // return vl+vr; // } //} 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());} }