{"problem":{"name":"Neo-lexicographic Ordering","description":{"content":"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 permutat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc219_c"},"statements":[{"statement_type":"Markdown","content":"Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.\nThe new alphabetical order is represented by a string $X$, which is a permutation of `a`, `b`, $\\ldots$, `z`. The $i$\\-th character of $X$ $(1 \\leq i \\leq 26)$ would be the $i$\\-th smallest English lowercase letter in the new order.\nThe kingdom has $N$ citizens, whose names are $S_1, S_2, \\dots, S_N$, where each $S_i$ $(1 \\leq i \\leq N)$ consists of lowercase English letters.  \nSort these names lexicographically according to the alphabetical order decided by Takahashi.\nWhat is the lexicographical order?Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings $S$ and $T$.\nBelow, let $S_i$ denote the $i$\\-th character of $S$. Also, if $S$ is lexicographically smaller than $T$, we will denote that fact as $S \\lt T$; if $S$ is lexicographically larger than $T$, we will denote that fact as $S \\gt T$.\n\n1.  Let $L$ be the smaller of the lengths of $S$ and $T$. For each $i=1,2,\\dots,L$, we check whether $S_i$ and $T_i$ are the same.\n2.  If there is an $i$ such that $S_i \\neq T_i$, let $j$ be the smallest such $i$. Then, we compare $S_j$ and $T_j$. If $S_j$ comes earlier than $T_j$ in alphabetical order, we determine that $S \\lt T$ and quit; if $S_j$ comes later than $T_j$, we determine that $S \\gt T$ and quit.\n3.  If there is no $i$ such that $S_i \\neq T_i$, we compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we determine that $S \\lt T$ and quit; if $S$ is longer than $T$, we determine that $S \\gt T$ and quit.\n\n## Constraints\n\n*   $X$ is a permutation of `a`, `b`, $\\ldots$, `z`.\n*   $2 \\leq N \\leq 50000$\n*   $N$ is an integer.\n*   $1 \\leq |S_i| \\leq 10 \\, (1 \\leq i \\leq N)$\n*   $S_i$ consists of lowercase English letters. $(1 \\leq i \\leq N)$\n*   $S_i \\neq S_j$ $(1 \\leq i \\lt j \\leq N)$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$X$\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc219_c","tags":[],"sample_group":[["bacdefghijklmnopqrstuvwxzy\n4\nabx\nbzz\nbzy\ncaa","bzz\nbzy\nabx\ncaa\n\nIn 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."],["zyxwvutsrqponmlkjihgfedcba\n5\na\nab\nabc\nac\nb","b\na\nac\nab\nabc"]],"created_at":"2026-03-03 11:01:14"}}