#include 
      
      
        <
      
      
        iostream
      
      
        >
      
      
        

        #include 
      
      
        <
      
      
        string
      
      
        >
      
      
        

        #include 
      
      
        <
      
      
        vector
      
      
        >
      
      
        

        #include 
      
      
        <
      
      
        algorithm
      
      
        >
      
      
        

      
      
        using
      
      
      
      
        namespace
      
      
         std;
        

        

        typedef pair
      
      
        <
      
      
        int
      
      
        , 
      
      
        int
      
      
        >
      
      
         word_index;
        

        

        typedef pair
      
      
        <
      
      
        int
      
      
        , 
      
      
        int
      
      
        >
      
      
         lv1_index;
        

        

      
      
        #define
      
      
         NOT_VALUE 0xffffffff
      
      
        

        

        typedef 
      
      
        struct
      
      
         dp_item {
        

      
      
        int
      
      
         min_word_amount;
        

      
      
        int
      
      
         min_word_seq[
      
      
        200
      
      
        ]; 
      
      
        //
      
      
        最長的word序列也就是100個單字母組成
      
      
        

      
      
        } dp_item;
        

        

        

      
      
        string
      
      
         words[
      
      
        100010
      
      
        ];
        

        dp_item dp[
      
      
        200
      
      
        ] 
      
      
        =
      
      
         { 
      
      
        0
      
      
         };  
      
      
        //
      
      
        號碼最長是100個字符
      
      
        

      
      
        lv1_index index_lv1[
      
      
        100
      
      
        ]; 
      
      
        //
      
      
        一級索引使用數組，不用vector，因為這樣可以更方便地根據 索引項的單詞長度，隨機訪問一級索引，單個詞最長也就50個字符
      
      
        

      
      
        

      
      
        bool
      
      
         cmp_index(
      
      
        const
      
      
         word_index 
      
      
        &
      
      
        a, 
      
      
        const
      
      
         word_index 
      
      
        &
      
      
        b) {
        

        

      
      
        if
      
      
        ( a.second 
      
      
        ==
      
      
         b.second )
        

      
      
        return
      
      
         a.first 
      
      
        <
      
      
         b.first;
        

        

      
      
        return
      
      
         a.second 
      
      
        <
      
      
         b.second;
        

        }
        

        

      
      
        char
      
      
         letter_to_num(
      
      
        char
      
      
         letter) {
        

      
      
        switch
      
      
        (letter) {
        

      
      
        case
      
      
      
      
        '
      
      
        i
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        j
      
      
        '
      
      
        :                    
      
      
        return
      
      
      
      
        '
      
      
        1
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        a
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        b
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        c
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        2
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        d
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        e
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        f
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        3
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        g
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        h
      
      
        '
      
      
        :                    
      
      
        return
      
      
      
      
        '
      
      
        4
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        k
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        l
      
      
        '
      
      
        :                    
      
      
        return
      
      
      
      
        '
      
      
        5
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        m
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        n
      
      
        '
      
      
        :                    
      
      
        return
      
      
      
      
        '
      
      
        6
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        p
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        r
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        s
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        7
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        t
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        u
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        v
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        8
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        w
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        x
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        y
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        9
      
      
        '
      
      
        ;
        

      
      
        case
      
      
      
      
        '
      
      
        o
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        q
      
      
        '
      
      
        : 
      
      
        case
      
      
      
      
        '
      
      
        z
      
      
        '
      
      
        :        
      
      
        return
      
      
      
      
        '
      
      
        0
      
      
        '
      
      
        ;
        

            }
        

        }
        

        

      
      
        bool
      
      
         match(
      
      
        const
      
      
      
      
        string
      
      
      
      
        &
      
      
        sub_num, 
      
      
        const
      
      
      
      
        string
      
      
      
      
        &
      
      
        word) {
        

      
      
        for
      
      
        ( 
      
      
        int
      
      
         i
      
      
        =
      
      
        0
      
      
        ; i 
      
      
        <
      
      
         sub_num.length(); i
      
      
        ++
      
      
         ) 
        

      
      
        if
      
      
        ( letter_to_num(word[i]) 
      
      
        !=
      
      
         sub_num[i] )
        

      
      
        return
      
      
      
      
        false
      
      
        ;
        

        

      
      
        return
      
      
      
      
        true
      
      
        ;
        

        }
        

        

      
      
        int
      
      
         main() {
        

        

      
      
        string
      
      
         number;
        

            vector
      
      
        <
      
      
         word_index 
      
      
        >
      
      
         sorted_index_lv2, sorted_index_lv1;
        

            vector
      
      
        <
      
      
         word_index 
      
      
        >
      
      
        ::iterator it;
        

      
      
        int
      
      
         word_amount 
      
      
        =
      
      
      
      
        0
      
      
        , i, j, d, k, word_len, number_len, idx;
        

      
      
        int
      
      
         min, min_choice, min_choice_word;
        

        

            cin
      
      
        >>
      
      
        number;
        

      
      
        while
      
      
        (number 
      
      
        !=
      
      
      
      
        "
      
      
        -1
      
      
        "
      
      
        ) {
        

                memset(dp, NOT_VALUE, 
      
      
        sizeof
      
      
        (dp));
        

                memset(index_lv1, NOT_VALUE, 
      
      
        sizeof
      
      
        (index_lv1));
        

                sorted_index_lv2.clear();
        

        

                number_len 
      
      
        =
      
      
         number.length();
        

        

                cin
      
      
        >>
      
      
        word_amount;
        

        

      
      
        if
      
      
        ( word_amount 
      
      
        ==
      
      
      
      
        0
      
      
      
      
        ||
      
      
         number_len 
      
      
        ==
      
      
      
      
        0
      
      
         ) {
        

                    cout
      
      
        <<
      
      
        "
      
      
        No solution.
      
      
        "
      
      
        <<
      
      
        endl;
        

                    cin
      
      
        >>
      
      
        number;
        

      
      
        continue
      
      
        ;
        

                }
        

        

      
      
        for
      
      
        ( i
      
      
        =
      
      
        0
      
      
        ;i
      
      
        <
      
      
        word_amount;i
      
      
        ++
      
      
         )
        

                    cin
      
      
        >>
      
      
        words[i];
        

        

      
      
        for
      
      
        ( i
      
      
        =
      
      
        0
      
      
        ;i
      
      
        <
      
      
        word_amount;i
      
      
        ++
      
      
         )
        

                    sorted_index_lv2.push_back(make_pair(i, (
      
      
        int
      
      
        )(words[i].length())));
        

        

                sort(sorted_index_lv2.begin(), sorted_index_lv2.end(), cmp_index);  
      
      
        //
      
      
        完成二級索引
      
      
        

      
      
        

                word_len 
      
      
        =
      
      
         sorted_index_lv2[
      
      
        0
      
      
        ].second;
        

                index_lv1[word_len] 
      
      
        =
      
      
         make_pair(
      
      
        0
      
      
        , 
      
      
        1
      
      
        );
        

        

      
      
        for
      
      
        ( i
      
      
        =
      
      
        1
      
      
        ; i
      
      
        <
      
      
        sorted_index_lv2.size(); i
      
      
        ++
      
      
         ) {  
      
      
        //
      
      
        構造一級索引
      
      
        

      
      
      
      
        if
      
      
        ( sorted_index_lv2[i].second 
      
      
        !=
      
      
         word_len ) {
        

                        word_len 
      
      
        =
      
      
         sorted_index_lv2[i].second; 
      
      
        //
      
      
        長度為舊word_len的單詞沒有了，到新的word_len長度了
      
      
        

      
      
                        index_lv1[word_len] 
      
      
        =
      
      
         make_pair(i, 
      
      
        1
      
      
        ); 
      
      
        //
      
      
        記錄第一個長度為word_len的單詞在sorted_index_lv2中的位置i
      
      
        

      
      
                    }
        

      
      
        else
      
      
         { 
        

                        index_lv1[word_len].second
      
      
        ++
      
      
        ;    
      
      
        //
      
      
        找到多一個長度為word_len的單詞
      
      
        

      
      
                    }
        

                }
        

        

                dp[
      
      
        0
      
      
        ].min_word_amount 
      
      
        =
      
      
      
      
        0
      
      
        ;
        

      
      
        for
      
      
        ( i
      
      
        =
      
      
        1
      
      
        ;i 
      
      
        <=
      
      
         number_len;i
      
      
        ++
      
      
         ) {
        

        

      
      
        for
      
      
        ( k
      
      
        =
      
      
        0
      
      
        , min_choice 
      
      
        =
      
      
      
      
        -
      
      
        1
      
      
        ; k 
      
      
        <
      
      
         i; k
      
      
        ++
      
      
        ) {
        

      
      
        if
      
      
        ( dp[k].min_word_amount 
      
      
        ==
      
      
         NOT_VALUE ) 
      
      
        //
      
      
        沒有長k的匹配前綴，就算后面有長i-k的匹配后綴，也沒用
      
      
        

      
      
      
      
        continue
      
      
        ;
        

        

                        idx 
      
      
        =
      
      
         index_lv1[i
      
      
        -
      
      
        k].first; 
      
      
        //
      
      
        獲取后綴長度的單詞組的一級索引
      
      
        

      
      
        

      
      
        if
      
      
        ( idx 
      
      
        ==
      
      
         NOT_VALUE )  
      
      
        //
      
      
         沒有長度為k的單詞
      
      
        

      
      
      
      
        continue
      
      
        ;
        

        

      
      
        //
      
      
        遍歷所有長度為i的單詞
      
      
        

      
      
      
      
        for
      
      
        ( j
      
      
        =
      
      
        idx, d
      
      
        =
      
      
        0
      
      
        ; d 
      
      
        <
      
      
         index_lv1[i
      
      
        -
      
      
        k].second; d
      
      
        ++
      
      
        , j
      
      
        ++
      
      
         ) { 
      
      
        //
      
      
        second保存的是，在二級索引中，有多少個索引項的單詞是長度為i-k的。
      
      
        

      
      
        

      
      
        if
      
      
        ( dp[i].min_word_amount 
      
      
        ==
      
      
         NOT_VALUE 
      
      
        ||
      
      
         dp[i].min_word_amount 
      
      
        >
      
      
         dp[k].min_word_amount 
      
      
        +
      
      
      
      
        1
      
      
        ) { 
      
      
        //
      
      
        當k=0時，計算對象的就是后綴長度為i的單詞
      
      
        

      
      
        

      
      
        if
      
      
        ( match(number.substr(k, i
      
      
        -
      
      
        k), words[sorted_index_lv2[j].first]) ) { 
      
      
        //
      
      
        判斷長度為i-k的單詞是否符合號碼的相應部分
      
      
        

      
      
                                    dp[i].min_word_amount 
      
      
        =
      
      
         dp[k].min_word_amount 
      
      
        +
      
      
      
      
        1
      
      
        ;
        

                                    min_choice 
      
      
        =
      
      
         k;
        

                                    min_choice_word 
      
      
        =
      
      
         sorted_index_lv2[j].first;
        

      
      
        break
      
      
        ; 
      
      
        //
      
      
        同一長度的單詞，選第一個能匹配的就夠
      
      
        

      
      
                                }
        

                            }
        

                        }
        

                    }
        

        

      
      
        if
      
      
        ( dp[i].min_word_amount 
      
      
        !=
      
      
         NOT_VALUE ) { 
      
      
        //
      
      
        長度為i的前綴串擁有最短匹配單詞組
      
      
        

      
      
        

      
      
        if
      
      
        ( dp[min_choice].min_word_amount 
      
      
        >
      
      
      
      
        0
      
      
         ) 
        

                            memcpy(dp[i].min_word_seq, dp[min_choice].min_word_seq, 
      
      
        sizeof
      
      
        (
      
      
        int
      
      
        ) 
      
      
        *
      
      
         dp[min_choice].min_word_amount); 
      
      
        //
      
      
        不用擔心最初序列長度是0，因為什么都不復制 ^_^
      
      
        

      
      
        

                        dp[i].min_word_seq[ dp[i].min_word_amount 
      
      
        -
      
      
      
      
        1
      
      
         ] 
      
      
        =
      
      
         min_choice_word;
        

                    }
        

                }
        

        

      
      
        if
      
      
        ( dp[number_len].min_word_amount 
      
      
        ==
      
      
         NOT_VALUE ) {
        

                    cout
      
      
        <<
      
      
        "
      
      
        No solution.
      
      
        "
      
      
        <<
      
      
        endl;
        

                }
        

      
      
        else
      
      
         {
        

      
      
        for
      
      
        ( i 
      
      
        =
      
      
      
      
        0
      
      
        ; i 
      
      
        <
      
      
         dp[number_len].min_word_amount 
      
      
        -
      
      
      
      
        1
      
      
        ; i
      
      
        ++
      
      
         ) 
        

                        cout
      
      
        <<
      
      
        words[ dp[number_len].min_word_seq[i] ]
      
      
        <<
      
      
        "
      
      
      
      
        "
      
      
        ;
        

                    cout
      
      
        <<
      
      
        words[ dp[number_len].min_word_seq[i] ]
      
      
        <<
      
      
        endl;
        

                }
        

        

                cin
      
      
        >>
      
      
        number;
        

            }
        

        

      
      
        return
      
      
      
      
        0
      
      
        ;
        

        }