题目描述

题目译自 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

数据范围与提示

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