#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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgp2b2lkIHJldmVyc2UoY2hhcipzLGludCBuKSB7CiAgICBwcmludGYoInJldmVyc2U9JXMgJWRcbiIsIHMsbik7CiAgICBjaGFyIHQ7CiAgICB3aGlsZShuPjApIHsKICAgICAgICB0PSpzOwogICAgICAgICpzPSoocytuLTEpOwogICAgICAgICoocytuLTEpPXQ7CiAgICAgICAgbi09MjsKICAgIH0KfQoKdm9pZCBmKGNoYXIqcykgewogICAgaW50IGxlbj1zdHJsZW4ocyk7CiAgICBjaGFyKnc9bWFsbG9jKGxlbipzaXplb2YoY2hhcikrMik7CiAgICBzcHJpbnRmKHcsIjAlcyIsIHMpOwogICAgY2hhcipwPXcrbGVuOwogICAgaW50IG49MDsKICAgIHdoaWxlKCpwPT0nMCcpCiAgICAgICAgLS1wOwogICAgd2hpbGUoKnA9PScxJykKICAgICAgICAtLXAsKytuOwogICAgcmV2ZXJzZShwLDIpOwogICAgcCs9MjsKICAgIHJldmVyc2UocCxsZW4tKHAtdykrMSk7CiAgICBpZiAoKnc9PScwJykKICAgICAgICArK3c7CiAgICBwcmludGYoImlucHV0ICA9ICVzXG5vdXRwdXQgPSAlc1xuXG4iLCBzLHcpOwp9CgppbnQgbWFpbigpCnsKICAgIGYoIjExMSIpOwogICAgZigiMTExMCIpOwogICAgZigiMTAxMTAwIik7CiAgICBmKCIxMDAwMTEiKTsKICAgIGYoIjEwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMTAxMDAiKTsKICAgIGYoIjEwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMTAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDEiKTsKICAgIHJldHVybiAwOwp9Cg==