← 返回题目列表

Codeforces · 1110/H

H. 适度的子串

中文机器翻译题面 查看原题

给你两个整数 $$$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$$$ 次)。