在一个非常古老的国家,以下游戏很流行。两个人玩游戏。最初,第一个玩家写入一个字符串 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。