P6661 [POI 2019/2020 R1] Pomniejszenie / Reduction

Bajtek and Bitek are brothers (Bajtek is the older one), and they want to play a game.

The rules are: whoever writes the larger number wins. Suppose Bajtek writes $A$, and Bitek writes $B$. $A$ and $B$ have the same length, and they may have leading zeros. However, Bajtek wins every time (that is, always $A \ge B$), so Bajtek wants to lose once. Now he can change **exactly** $k$ digits of $A$ so that $A$ becomes smaller than $B$. Find the maximum possible value of $A$ after modification such that $A < B$. If it is impossible to make $A$ smaller than $B$, output `-1`. Because the brothers really like this game, they will play $t$ rounds, meaning there will be $t$ modifications and checks.

The first line contains an integer $t$, the number of rounds. The next $t$ lines each contain three integers $A, B, k$, representing the number written by Bajtek, the number written by Bitek, and the allowed number of modifications.

Output $t$ lines, each containing one integer: the maximum value of $A$ after modification such that $A < B$. If no modification of $A$ can make it smaller than $B$, output `-1`.

#### Sample Explanation The first two additional samples correspond to sample1/2.in and sample1/2.out in the additional files. The third additional sample is sample3.zip. #### Constraints **This problem uses bundled testdata.** Let $n$ be the length of $A$ and $B$: - Subtask 1 (18 pts): $1 \le n \le 5$. - Subtask 2 (20 pts): $1 \le n \le 5000$. - Subtask 3 (20 pts): $1 \le n \le 10^5$, $k = 1$. - Subtask 4 (42 pts): no special constraints. For $100\%$ of the testdata, $1 \le t \le 100$, $1 \le k \le n \le 10^5$, and $A \ge B$. #### Notes Translated from [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) C [Pomniejszenie](https://sio2.mimuw.edu.pl/c/oi27-1/p/pom/)。 Translated by ChatGPT 5