题目描述

P 国是一个神奇的国度，在这里，所有的车牌都是长度恰好为 $k$ 且仅包含小写英文字母的字符串。

然而，再神奇的国度也避免不了交通堵塞的问题。为此，P 国采用"限号出行"的方式进行分流。具体来说，决定一个车牌 $s$ 在当天能否出行的是若干条形如 $(x_i,y_i)$ 的规则，若 $s$ 中存在一个位置 $1\le j< k$，满足 $s_j=x_i$ 且 $s_{j+1}=y_i$，则认为 $s$ 违反了第 $i$ 条规则，$s$ 也就无法在当天出行。

今天是小 M 大喜的日子，因为他喜提了一辆新车，但这辆新车还没有车牌。小 M 得到了一个长度为 $n$ 且仅包含小写英文字母的字符串 $t$ 作为"原始车牌"，他需要从 $t$ 中删掉恰好 $n-k$ 个字符，也即取出一个长度恰好为 $k$ 的子序列，来作为新车的车牌。同时，小 M 得知了今天的 $m$ 条"限号出行"规则，他希望你能帮助他找出一个能在今天立即出行的车牌，或是判断无解。由于小 M 对字典序有着强烈的执念，若有多种可行的车牌，你需要找到字典序最小的那一个。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$（$1\le T\le 10^5$），表示测试数据的组数。

接下来，对于每组测试数据：

第一行包含三个非负整数，分别表示 $n,m$ 和 $k$（$1\le k\le n\le \sum n\le 2\times 10^5$，$0\le m\le \min(n,26)^2$）。

第二行包含一个长度为 $n$ 的字符串，表示 $t$。

接下来 $m$ 行，每行包含两个由单个空格隔开的小写英文字母，分别表示 $x_i$ 和 $y_i$，保证 $\forall i\ne j,(x_i,y_i)\ne(x_j,y_j)$。

输出格式

对于每组测试数据，输出一行一个字符串，若有解则输出字典序最小的可行车牌，否则输出 -1。

样例

输入

2
8 3 5
bacbabca
a b
b a
c c
4 1 3
aaaa
a a

输出

acaca
-1