给你两个整数 $$$l$$$ 和 $$$r$$$。
如果 $$$l \le x \le r$$$,我们称整数 $$$x$$$ 为适度整数。
找到一个长度为 $$$n$$$ 的字符串,由数字组成,该字符串具有最大可能数量的子字符串,这些子字符串构成一个适度的整数。具有前导零的子字符串不计算在内。如果有很多答案,请找到字典顺序最小的一个。
如果某个数字作为子串出现多次,那么在计算适度子串的数量时,它也会被计算多次。
输入
第一行包含一个整数 $$$l$$$ ($$$1 \le l \le 10^{800}$$$)。
第二行包含一个整数 $$$r$$$ ($$$l \le r \le 10^{800}$$$)。
第三行包含一个整数$$$n$$$ ($$$1 \le n \le 2\,000$$$)。
输出
在第一行中,打印适度子字符串的最大可能数量。
在第二行中,打印长度为 $$$n$$$ 的字符串,该字符串恰好具有该数量的适度子字符串。
如果有多个这样的字符串,则打印其中按字典顺序最小的一个。
示例
输入 #1
1 10 3
输出 #1
3 101
输入 #2
1 11 3
输出 #2
5 111
输入 #3
12345 12346 6
输出 #3
1 012345
注意
在第一个示例中,字符串“101”具有适度的子字符串“1”、“10”、“1”。
在第二个示例中,字符串“111”具有适度的子字符串“1”($$$3$$$ 次)和“11”($$$2$$$ 次)。