AdditionalFile3234.zip

#3234. 「POI2020 R1」Pomniejszenie

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

题目译自 POI XXVII - I etap 「Pomniejszenie」

给出两个数字串 $A$ 和 $B$，保证 $A \ge B$。你可以修改 $A$ 里面恰好 $k$ 个数字，求出比 $B$ 小的最大数字。

输入格式

输入数据第一行包含一个整数 $t$，表示测试数据组数。对于每组测试数据：

第一行包含三个非负整数 $A$，$B$ 和 $k$。保证 $A$ 和 $B$ 的长度是一样的，并且可能有前导零。$k$ 是一个正整数，并且不会超过 $A$ 和 $B$ 的长度。

输出格式

对于每组数据，输出一个满足下面条件的整数 $C$：

• $C$ 的长度必须和 $A$ 以及 $B$ 的一样，可以包含前导零。

• $C$ 是由 $A$ 恰好修改了 $k$ 个字符得到。

• $C$ 要尽可能的大，并且 $C$ 要小于 $B$。

如果不存在满足按上面条件的 $C$，请输出$-1$。

样例

输入

4
555 333 1
0555 0551 3
0555 0333 4
9 9 1

输出

255
0499
-1
8

附加样例参见 pom/pom*.in 和 pom/pom*.out：

• 附加样例 $1$：$t = 100$；$A$ 依次是 $20\ 000, 20\ 001, \dots$；$B$ 一直是 $20\ 000$；$k=1$；

• 附加样例 $2$：$t = 100$；对于每组数据 $n = 5000$，并且 $A$ 和 $B$ 里仅包含数字9；$k$ 依次是 $4901, \dots, 5000$；

• 附加样例 $3$：$t = 100$；对于每组数据 $n = 10^5$，并且 $A$ 里包含数字9，$B$ 里仅包含数字 2；$k$ 依次是 $1, \dots, 100$。

数据范围与提示

令 $n$ 是数字串 $A$ 和 $B$ 的长度，保证对于所有数据有 $1 \le t \le 100$。