CF117B.Very Interesting Game

In a very ancient country the following game was popular. Two people play the game. Initially first player writes a string _s_1, consisting of exactly nine digits and representing a number that does not exceed a. After that second player looks at _s_1 and writes a string _s_2, consisting of exactly nine digits and representing a number that does not exceed b. Here a and b are some given constants, _s_1 and _s_2 are chosen by the players. The strings are allowed to contain leading zeroes.

If a number obtained by the concatenation (joining together) of strings _s_1 and _s_2 is divisible by mod, then the second player wins. Otherwise the first player wins. You are given numbers a, b, mod. Your task is to determine who wins if both players play in the optimal manner. If the first player wins, you are also required to find the lexicographically minimum winning move.

在某个非常古老的国家，曾流行这样一种游戏：两人参与游戏。游戏开始时，先手玩家写下字符串 $s_1$，该字符串恰好由九位数字组成，且其所表示的数不超过 $a$；随后，后手玩家观察 $s_1$，写下字符串 $s_2$，该字符串也恰好由九位数字组成，且其所表示的数不超过 $b$。其中 $a$ 和 $b$ 是给定的常数，$s_1$ 和 $s_2$ 由双方玩家各自选择。字符串允许包含前导零。

若将字符串 $s_1$ 和 $s_2$ 拼接（即连接在一起）所得的数字能被 $mod$ 整除，则后手玩家获胜；否则先手玩家获胜。现给定整数 $a$、$b$、$mod$，你的任务是判断：当双方均以最优策略进行游戏时，谁将获胜。若先手玩家获胜，你还需找出字典序最小的获胜第一步（即满足条件的字典序最小的 $s_1$）。

The first line contains three integers a, b, mod (0 ≤ a, b ≤ 109, 1 ≤ mod ≤ 107).

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

If the first player wins, print "1" and the lexicographically minimum string _s_1 he has to write to win. If the second player wins, print the single number "2".

如果先手玩家获胜，输出“1”以及他为获胜必须写出的字典序最小的字符串 $s_1$；如果后手玩家获胜，则仅输出单个数字“2”。

The lexical comparison of strings is performed by the < operator in modern programming languages. String x is lexicographically less than string y if exists such i (1 ≤ i ≤ 9), that x__i < y__i, and for any j (1 ≤ j < i) x__j = y__j. These strings always have length 9.

现代编程语言中，字符串的字典序比较通过 < 运算符实现。字符串 $x$ 在字典序上小于字符串 $y$，当且仅当存在某个 $i$（$1 \le i \le 9$），使得 $x_i < y_i$，且对任意 $j$（$1 \le j < i$）均有 $x_j = y_j$。这些字符串的长度恒为 9。