#include <iostream>
 
#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}
 
int main(){
	std::cout<<g("1")<<"\n";
	std::cout<<g("11")<<"\n";
	std::cout<<g("111")<<"\n";
	std::cout<<g("1011")<<"\n";
	std::cout<<g("1111")<<"\n";
	std::cout<<g("10111")<<"\n";
	std::cout<<g("101100")<<"\n";
	std::cout<<g("100000")<<"\n";
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKI2luY2x1ZGUgPHN0cmluZz4Kc3RkOjpzdHJpbmcgZyhzdGQ6OnN0cmluZyBzKXtpbnQgaSx6O2lmKHM9PSIxIilyZXR1cm4iMTEiO2ZvcihpPXo9MDtpPHMubGVuZ3RoKCk7aSsrKWlmKHNbaV09PScxJyl6Kys7aS0tO2lmKHolMil7Y2hhciBjPXNbaV07cy5lcmFzZShpKTtzPWcocyk7cys9Yzt9ZWxzZXtzW2ldPXNbaV09PTQ5PzQ4OjQ5O31yZXR1cm4gczt9CgppbnQgbWFpbigpewoJc3RkOjpjb3V0PDxnKCIxIik8PCJcbiI7CglzdGQ6OmNvdXQ8PGcoIjExIik8PCJcbiI7CglzdGQ6OmNvdXQ8PGcoIjExMSIpPDwiXG4iOwoJc3RkOjpjb3V0PDxnKCIxMDExIik8PCJcbiI7CglzdGQ6OmNvdXQ8PGcoIjExMTEiKTw8IlxuIjsKCXN0ZDo6Y291dDw8ZygiMTAxMTEiKTw8IlxuIjsKCXN0ZDo6Y291dDw8ZygiMTAxMTAwIik8PCJcbiI7CglzdGQ6OmNvdXQ8PGcoIjEwMDAwMCIpPDwiXG4iOwoJcmV0dXJuIDA7Cn0=