题目背景

2025 年广西中小学生程序设计挑战赛入门组 T2

题目描述

小明是查字典高手，每次都能快速查找到自己不会的单词。这一天，小明在路上捡到了好几本字典，打开一看，发现这些字典中，字母的顺序和常规的不一样。

他很好奇，如果有两个不同的字符串 $s$ 和 $t$，他想知道哪个字符串在当前这本字典中的字典序更小。

设字符串 $s$ 长度为 $n$，字符串 $t$ 长度为 $m$，其中 $s = s_0 s_1 \cdots s_{n-1}$，$t = t_0 t_1 \cdots t_{m-1}$。

对于字典序的解释：

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

找到最小的正整数 $k(0\le k < \min(n, m))$，使得 $s_k \ne t_k$。若 $s_k < t_k$，则序列 $s$ 的字典序小于 $t$。

若不存在这样的 $k$，则当 $n<m$ 时序列 $s$ 的字典序小于 $t$。

输入格式

从 dictionary.in 文件读入数据。

第一行包含两个正整数 $n,m$，分别表示字符串 $s,t$ 的长度。

第二行有两个仅包含小写字母的字符串 $s,t$。

第三行输入一个正整数 $T$，代表有 $T$ 本字典。

接下来有 $T$ 行数据，第 $i$ 行数据包含一个长度为 $26$ 的仅包含小写字母的字符串 $D_i$，代表第 $i$ 本字典中的字符顺序。

输出格式

输出到 dictionary.out 文件。

第 $i$ 行输出一个字母。

若 $s$ 字典序小于 $t$，则输出 $s$；否则输出 $t$。

数据保证不会出现字典序相同的情况。

样例

4 4
adeg
abah
2
abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba

t
s

3 4
abc
abcd
2
abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba

s
s

5 5
ypdmz
ypdms
3
dbvygoufzamnphlsjcxewtrikq
ntsdkjbuhefozpwyirmcqgxlav
jswtzbriyfpvqmkunglhxodeca

s
t
t

说明/提示

对于 $30\%$ 的数据，字符串 $s,t$ 的长度不超过 $100$。

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