题目内容

给小塔$n$个字符串，请你对这$n$个字符串按照以下规则从小到大排序。

对于任意两个字符串$s$和$t$，在排序后应当满足：

若$s$是$t$的一个前缀，则$s$在排序后的下标小于等于t的在排序后的下标。

若存在整数$i$，使得$s$的前$i-1$个字符和$t$的前$i-1$个字符相同，且$s$和$t$的第$i$个字符不同，则比较第$i$个字符的大小关系(字符的大小关系顺序由输入数据给出)。若$s$的第$i$个字符小于等于$t$的第$i$个字符，则$s$在排序后的下标小于等于t的在排序后的下标。

容易发现，上述排序方法排序结果是唯一的。

输入描述

第一行输入一个字符串，包含$26$个互不相同的小写字母。记$rank(c)$表示字母$c$是该字符串的第$rank(c)$个字符，则字母$a$小于等于字母$b$当且仅当$rank(a)≤rank(b)$。

第二行输入一个整数$n(1≤n≤1000)$，表示待排序字符串的数量。

接下来$n$行，每行一个仅包含小写字符的字符串$s_i(|s_i|≤1000)$，表示一个待排序的字符串。

输出描述

按照排序后字符串位置下标从小到大的顺序输出$n$行，每行一个字符串，表示排序的结果。

样例1

输入

abcdefghijklmnopqrstuvwxyz
3
aaa
aac
aaaa

输出

aaa
aaaa
aac

样例2

输入

zyxwvutsrqponmlkjihgfedcba
3
aaa
aac
aaaa

输出

aac
aaa
aaaa