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