#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void reverse(char*s,int n) {
    printf("reverse=%s %d\n", s,n);
    char t;
    while(n>0) {
        t=*s;
        *s=*(s+n-1);
        *(s+n-1)=t;
        n-=2;
    }
}

void f(char*s) {
    int len=strlen(s);
    char*w=malloc(len*sizeof(char)+2);
    sprintf(w,"0%s", s);
    char*p=w+len;
    int n=0;
    while(*p=='0')
        --p;
    while(*p=='1')
        --p,++n;
    reverse(p,2);
    p+=2;
    reverse(p,len-(p-w)+1);
    if (*w=='0')
        ++w;
    printf("input  = %s\noutput = %s\n\n", s,w);
}

int main()
{
    f("111");
    f("1110");
    f("101100");
    f("100011");
    f("1000000000000000000000000000000000010100");
    f("1000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000001");
    return 0;
}