Read problem statements in [Russian], [Mandarin Chinese], [Bengali], and [Vietnamese] as well.

You are given a string S consisting of N digits from 0 to 9. You want to obtain a palindrome from S using some operations.

There are M different types of operations you can make on S. Each operation is described by three integers X, Y and W. In this operation, if there is a digit equal to X in S, you can replace X with Y using W coins. For example, if X = 4, Y= 5, W = 10 and S = 1448, you make S equal to either 1458 or 1548 using 10 coins.

You can do the operations in any order. One type of operation can be done multiple times. You can use at most K coins total in all operations. Among all the palindromes that can be obtained from S, output the lexicographically maximum palindrome.

If two strings A and B have the same length, we say that A is lexicographically larger than B if there exists an index i so that $A_{1}=B_{1},A_{2}=B_{2},\ldots,A_{i-1}=B_{i-1}, A_{i}>B_{i}$.

Print -1 if it is impossible to obtain a palindrome from S using at most K coins.

------ Input Format ------

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• The first line of each test case contains three integers N, M, and K - the length of the string, the number of operation types, and the maximum number of coins to spend, respectively.
• The second line contains a string S of length N.
• Each of the next M lines contains three integers X_{i}, Y_{i} and W_{i} - the parameters of the i-th type of operation.

------ Output Format ------

For each test case, output the lexicographically maximum palindrome which can be obtained from the given string S using at most K coins. Print -1 if it is impossible to obtain a palindrome.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 90$
$0 ≤ K, W_{i} ≤ 10^{9}$
$0 ≤ X_{i}, Y_{i} ≤ 9$, $X_{i}\ne Y_{i}$
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------
3
5 10 10
75643
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 0 1
4 5 1000000
1895
2 3 10
3 1 9
1 2 5
5 6 99
8 9 45
6 4 12
141746
1 5 3
5 7 2
7 9 10
6 1 5
----- Sample Output 1 ------
95759
-1
147741
----- explanation 1 ------
- In the first test case, we convert $7$ and $3$ into $9$ using two and six operations, respectively, $4$ into $5$ using one operation, and $6$ to $7$ using one operation. There is no way to obtain a palindrome which is lexicographically larger than $95759$ using ten operations.
- In the second test case, there is no possible way to convert $1$ and $5$ into equal digits. So we can't obtain a palindrome.
- In the third test case, we convert the $6$ in the last index of the given string into $1$ using the $4$-th type of operation. So $S$ becomes $141741$. Next, we convert $1$ in the third index into $5$ using the $1$-st type of operation. So $S$ becomes $145741$. Then we convert the $5$ in the third index of $S$ into $7$ using the $2$-nd type of operation. So $S$ becomes $147741$. The total cost is $5 + 3 + 2 = 10$ coins and the string we obtain after all operations is a palindrome. We can't obtain a lexicographically larger string than $147741$ using at most $12$ coins.

见题面

见题面