Palindromic number Solution Codeforces

You are given a string SS consisting of NN digits from 00 to 99. You want to obtain a palindrome from SS using some operations.

There are MM different types of operations you can make on SS. Each operation is described by three integers XXYY and WW. In this operation, if there is a digit equal to XX in SS, you can replace XX with YY using WW coins. For example, if X=4,Y=5,W=10X=4,Y=5,W=10 and S=1448S=1448, you make SS equal to either 14581458 or 15481548 using 1010 coins.

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

If two strings AA and BB have the same length, we say that AA is lexicographically larger than BB if there exists an index ii so that A1=B1,A2=B2,,Ai1=Bi1,Ai>BiA1=B1,A2=B2,…,Ai−1=Bi−1,Ai>Bi.

Print 1−1 if it is impossible to obtain a palindrome from SS using at most KK coins.

Input Format

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• The first line of each test case contains three integers NNMM, and KK – 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 SS of length NN.
• Each of the next MM lines contains three integers XiXiYiYi and WiWi – the parameters of the ii-th type of operation.

Output Format

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

Constraints

• 1T1031≤T≤103
• 1N1051≤N≤105
• 0M900≤M≤90
• 0K,Wi1090≤K,Wi≤109
• 0Xi,Yi90≤Xi,Yi≤9XiYiXi≠Yi
• The sum of NN over all test cases does not exceed 106106.

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

95759
-1
147741

Explanation

• In the first test case, we convert 77 and 33 into 99 using two and six operations, respectively, 44 into 55 using one operation, and 66 to 77 using one operation. There is no way to obtain a palindrome which is lexicographically larger than 9575995759 using ten operations.
• In the second test case, there is no possible way to convert 11 and 55 into equal digits. So we can’t obtain a palindrome.
• In the third test case, we convert the 66 in the last index of the given string into 11 using the 44-th type of operation. So SS becomes 141741141741. Next, we convert 11 in the third index into 55 using the 11-st type of operation. So SS becomes 145741145741. Then we convert the 55 in the third index of SS into 77 using the 22-nd type of operation. So SS becomes 147741147741. The total cost is 5+3+2=105+3+2=10 coins and the string we obtain after all operations is a palindrome. We can’t obtain a lexicographically larger string than 147741147741 using at most 1212 coins.