I. Restricted Plate Travel
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Country P is a magical country where every license plate is a string of length exactly $$$k$$$ containing only lowercase English letters.

However, even a magical country cannot avoid traffic congestion. Therefore, Country P adopts a "restricted plate travel" policy to reduce traffic. Specifically, whether a license plate $$$s$$$ is allowed to be used on a given day is determined by several rules of the form $$$(x_i,y_i)$$$. If there exists a position $$$1\le j \lt k$$$ in $$$s$$$ such that $$$s_j=x_i$$$ and $$$s_{j+1}=y_i$$$, then $$$s$$$ violates the $$$i$$$-th rule, and the vehicle with plate $$$s$$$ is not allowed to travel that day.

Today is a very happy day for Little M, because he has just bought a new car. However, the new car does not yet have a license plate. Little M has obtained a string $$$t$$$ of length $$$n$$$, containing only lowercase English letters, as the "original license plate". He needs to delete exactly $$$n-k$$$ characters from $$$t$$$, that is, choose a subsequence of length exactly $$$k$$$, to use as the license plate for his new car. At the same time, Little M has learned the $$$m$$$ restricted driving rules for today. He hopes you can help him find a license plate that is allowed to travel immediately today, or determine that no solution exists. Because Little M is strongly obsessed with lexicographical order, if there are multiple valid license plates, you need to find the lexicographically smallest one.

Input

This problem contains multiple test cases.

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^5$$$), indicating the number of test cases.

Then, for each test case:

The first line contains three non-negative integers $$$n,m$$$, and $$$k$$$ ($$$1\le k\le n\le \sum n\le 2\times 10^5$$$，$$$0\le m\le \min(n,26)^2$$$).

The second line contains a string $$$t$$$ of length $$$n$$$.

The next $$$m$$$ lines each contain two lowercase English letters separated by a single space, representing $$$x_i$$$ and $$$y_i$$$. It is guaranteed that $$$\forall i\ne j,(x_i,y_i)\ne(x_j,y_j)$$$.

Output

For each test case, output one line containing a string. If a solution exists, output the lexicographically smallest valid license plate. Otherwise, output -1.

Example
Input
2
8 3 5
bacbabca
a b
b a
c c
4 1 3
aaaa
a a
Output
acaca
-1