#include<bits/stdc++.h>
using namespace std;
map<string,bool>mp;
bool solve(string s){
    if(mp.find(s)!=mp.end())return mp[s];
    if(s=="1")return mp[s]=false;
    int cnt=0;
    for(auto ch:s)if(ch=='1')cnt++;
    if(cnt==0)return mp[s]=true;
//    if(cnt==1 && (s[0]=='1' || s[s.length()-1]=='1'))return mp[s]=true;

    if(solve(s.substr(1,s.length()-1)) && solve(s.substr(0,s.length()-1)))return mp[s]=false;
    return mp[s]=true;
}
string trans(string s){
    int cnt=0,len=s.length();
    string res="";
    for(int i=0;i<len;i++){
//        if(s[i]=='0')res.push_back('0');
//        else cnt++;
        cnt++;
        if(i==len-1 || s[i]!=s[i+1]){
//            for(int j=0;j<cnt;j++)res.push_back(s[i]);
            if(cnt&1)res.push_back(s[i]);
            cnt=0;
        }
    }
    return res;
}
map<string,int>ans;
void dfs(int pos,string s,int one,int pre){
    if(pos==10)return;
    if(one&1) {
        solve(s);
//        cout << s << ' '<<s.length() << ' ' << mp[s] << '\n';
        string tmp=trans(s);
        while(tmp!=trans(tmp))tmp=trans(tmp);
//        if(ans.find(tmp)==ans.end())ans[tmp]=mp[s];
//        else if(ans[tmp]!=mp[s]){
//            cout<<s<<' '<<tmp<<' '<<mp[s]<<'\n';
//        }
        if(tmp.length()&1){
            if(mp[s]==1){
                cout<<s<<' '<<tmp<<' '<<mp[s]<<'\n';
            }
        }else{
            if(mp[s]==0){
                cout<<s<<' '<<tmp<<' '<<mp[s]<<'\n';
            }
        }
    }
    if(pre!=1)dfs(pos+1,s+"1",one+1,1);//
    if(pre!=0) dfs(pos+1,s+"0",one,0);//
}
signed main(){
//    string s="12345";
//    cout<<s.substr(1,3);
    dfs(0,"",0,-1);
//    for(auto x:mp){
//        if(x.first.length()==8)
//            cout<<x.first<<' '<<x.second<<'\n';
//    }
//    for(auto x:ans){
//        cout<<x.first<<' '<<x.second<<'\n';
//    }
    return 0;
}