题目描述

在一个非常古老的国家流行过这样的游戏。两个人玩这个游戏。首先第一个人写下一个恰好由九个数字组成、且数值不超过 $a$ 的字符串 $s_1$。然后第二个人看着 $s_1$，写下一个恰好由九个数字组成、且数值不超过 $b$ 的字符串 $s_2$。这里 $a$、$b$ 是给定常数，$s_1$、$s_2$ 由玩家自行选择。字符串允许有前导零。

若把字符串 $s_1$ 与 $s_2$ 拼接起来得到的数能被 $mod$ 整除，则第二个人获胜；否则第一个人获胜。给你三个数 $a$、$b$、$mod$，请判断在双方都采取最优策略时谁会获胜。若第一个人获胜，还要求出他字典序最小的一步获胜着法。

输入格式

第一行包含三个整数 $a$、$b$、$mod$（$0 \le a, b \le 10^9$，$1 \le mod \le 10^7$）。

输出格式

若第一个人获胜，输出 "1" 以及他要写下的字典序最小的字符串 $s_1$；若第二个人获胜，只输出 "2"。

1 10 7

2

4 0 9

1 000000001

说明/提示

字符串的字典序比较与现代编程语言中的 < 运算符一致：若存在某个 $i$（$1 \le i \le 9$）使得 $x_i \lt y_i$，且对所有 $j$（$1 \le j \lt i$）有 $x_j = y_j$，则字符串 $x$ 字典序小于字符串 $y$。这些字符串的长度恒为 9。