← 返回题目列表

Codeforces · 117/B

B. 非常有趣的游戏

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

在一个非常古老的国家,以下游戏很流行。两个人玩游戏。最初,第一个玩家写入一个字符串 s1,它由 9 个数字组成,代表一个不超过 a 的数字。之后,第二个玩家查看 s1 并写入字符串 s2,该字符串由 9 个数字组成,代表一个不超过 b 的数字。这里a和b是一些给定的常数,s1和s2由玩家选择。字符串允许包含前导零。

如果字符串 s1 和 s2 连接(连接在一起)获得的数字可被 mod 整除,则第二个玩家获胜。否则第一个玩家获胜。给定数字 a、b、mod。您的任务是确定如果两名玩家都以最佳方式进行比赛,谁会获胜。如果第一个玩家获胜,您还需要找到字典顺序最小的获胜动作。

输入

第一行包含三个整数 a, b, mod (0 ≤ a, b ≤ 109, 1 ≤ mod ≤ 107)。

输出

如果第一个玩家获胜,则打印“1”以及他必须写入的按字典顺序排列的最小字符串 s1 才能获胜。如果第二个玩家获胜,则打印单个数字“2”。

示例

输入 #1

1 10 7

输出 #1

2

输入 #2

4 0 9

输出 #2

1 000000001

注意

字符串的词法比较是由现代编程语言中的 < 运算符执行的。如果存在这样的 i (1 ≤ i ≤ 9),即 xi < yi,并且对于任何 j (1 ≤ j < i) xj = yj,则字符串 x 按字典顺序小于字符串 y。这些字符串的长度始终为 9。