Neo-lexicographic Ordering

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300 points

---

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, …, z. The i-th character of X (1≤i≤26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S1,S2,…,S N
, where each Si(1≤i≤N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

What is the lexicographical order?

---

Constraints

X is a permutation of a, b, …, z.
2≤N≤50000
N is an integer.
1≤∣Si∣≤10 (1≤i≤N)
Si consists of lowercase English letters. (1≤i≤N)
Si=Sj (1≤i<j≤N)

---

Input

Input is given from Standard Input in the following format:
X
N
S1
S2
⋮
SN

---

Output

Print N lines. The i-th line (1≤i≤N) should contain the i-th smallest name when the citizens’ names are sorted according to the alphabetical order decided by Takahashi.

---

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

---

Sample Output 1

bzz
bzy
abx
caa
In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.
​

---

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

---

Sample Output 2

b
a
ac
ab
abc

---

AC

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n;i++)
#define inf 6666666
int main(){
    string x;
    cin >> x;
    int n;
    cin >> n;
    vector<pair<vector<int>, string>> v(n);
    rep(i, n){
        string s;
        cin >> s;
        vector<int> tmp(s.size());
        rep(j,s.size()){
            rep(k,26){
                if(x[k]==s[j]){
                    tmp[j] = k;
                    break;
                }
            }
        }
        v[i] = make_pair(tmp, s);
    }
    sort(v.begin(), v.end());
    rep(i, n)
            cout<< v[i].second << endl;
}

---