Timus 1414

#include<iostream>
#include<set>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<map>
using namespace std;

struct TINT {
    int no;
};

vector<string> ss;
map<long long,set<TINT> > mp;
set<TINT>::iterator it;
vector<long long> p_pow(21);

bool operator < (const TINT a,const TINT b) {
    return (ss[a.no]<ss[b.no]);
}

int i,j,k;

int main() {
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);
    string str;
    p_pow[0]=1;
    for (i=1;i<=20;i++)
        p_pow[i]=p_pow[i-1]*43;
    str="?sun"; ss.push_back("sun");
    TINT cur; cur.no=0;
    long long hs=0;
    for (i=0;i<4;i++) {
        if (str[i]>='a' && str[i]<='z')
            hs+=(str[i]-'a'+1)*p_pow[i];
        else if (str[i]>='0' && str[i]<='9')
            hs+=(str[i]-'0'+1+26)*p_pow[i];
        else if (str[i]=='?')
            hs+=(str[i]-'?'+1+11+26)*p_pow[i];
        mp[hs].insert(cur);
    }
    while (cin >> str) {
        if (str.length()==0) break;
        if (str[0]=='?') {
            long long hs=0;
            string str2="";
            for (i=0;i<str.length();i++) {
                if (str[i]>='a' && str[i]<='z')
                    hs+=(str[i]-'a'+1)*p_pow[i];
                else if (str[i]>='0' && str[i]<='9')
                    hs+=(str[i]-'0'+1+26)*p_pow[i];
                else if (str[i]=='?')
                    hs+=(str[i]-'?'+1+11+26)*p_pow[i];
                if (i>0) str2+=str[i];
            }
            cout << str2 << endl;
            if (mp[hs].size()!=0) {
                it=mp[hs].begin(); k=0;
                while (it!=mp[hs].end()) {
                    TINT cur=*it;
                    cout << "  " << ss[cur.no] << endl;
                    it++; k++;
                    if (k==20 || it==mp[hs].end()) break;
                }
            }
        } else {
            long long hs=0;
            string str2=""; str[0]='?';
            for (i=0;i<str.length();i++) {
                if (str[i]>='a' && str[i]<='z')
                    hs+=(str[i]-'a'+1)*p_pow[i];
                else if (str[i]>='0' && str[i]<='9')
                    hs+=(str[i]-'0'+1+26)*p_pow[i];
                else if (str[i]=='?')
                    hs+=(str[i]-'?'+1+11+26)*p_pow[i];
                if (i>0) str2+=str[i];
            }
            if (mp[hs].size()==0) {
                ss.push_back(str2);
                TINT cur; cur.no=ss.size()-1;
                long long hs=0;
                for (i=0;i<str.length();i++) {
                    if (str[i]>='a' && str[i]<='z')
                        hs+=(str[i]-'a'+1)*p_pow[i];
                    else if (str[i]>='0' && str[i]<='9')
                        hs+=(str[i]-'0'+1+26)*p_pow[i];
                    else if (str[i]=='?')
                        hs+=(str[i]-'?'+1+11+26)*p_pow[i];
                    mp[hs].insert(cur);
                }
            }
        }
    }
}