题目描述

小明是查字典高手，每次都能快速查找到自己不会的单词。这一天，小明在路上捡到了好几本字典，打开一看，发现这些字典中，字母的顺序和常规的不一样。 他很好奇，如果有两个不同的字符串 s 和 t，他想知道哪个字符串在当前这本字典中的字典序更小。

设字符串 s 长度为 n，字符串 t 长度为 m，其中 $s=s_ 0s_1…s_{n-1} , t=t_0t_1…t_{m-1}$ 。

对于字典序的解释：

当且仅当满足以下条件之一时，称字符串 s 的字典序比字符串 t 更小：

1.找到最小的正整数 $k(0≤k<min(n,m))$，使得 $s_k≠t_k$ 。若 sk 在当前字典中的顺序小于 $t_k$ ，则序列 s 的字典序小于 t。 2.若不存在这样的 k，则当n<m 时序列 s 的字典序小于 t。

输入格式

第一行包含两个正整数 n,m，分别代表字符串 s,t 的长度。 第二行有两个仅包含小写字母的字符串s,t。 第三行输入一个正整数 T，代表有 T 本字典。 接下来有 T 行数据，第 i 行数据包含一个长度为 26 的仅包含小写字母的字符串$D_i$ ，代表第 i 本字典中的字符顺序。

输出格式

输出T 行，第 i 行对应第 i 本字典的比较结果。若 s 字典序小于 t，则输出 s；否则输出t。 数据保证不会出现字典序相同的情况。

样例输入1

4 4  
adeg  
abah  
2  
abcdefghijklmnopqrstuvwxyz  
zyxwvutsrqpommlkjihgfedcba

样例输出1

t  
s

样例输入2

3 4  
abc  
abcd  
2  
abcdefghijklmnopqrstuvwxyz  
zyxwvutsrqpommlkjihgfedcba

样例输出2

s  
s

样例输入3

5 5  
ypdmz  
ypdms  
3  
dbvygoufzamnphlsjcxewtrikg  
ntsdkjbuhefozpwyirmcggxlav  
jswtzbriyfpvqmkunglhxodeca

样例输出3

s  
t  
t

说明提示

对于$30$的数据，字符串 $s,t$ 的长度不超过$100$。 对于$100$的数据，$1≤T≤10$，字符串 $s,t$ 的长度不超过$10^5$ 。