B. Очень занимательная игра
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В одной очень древней стране была популярна следующая игра. В игру играет два человека. Сначала первый игрок выписывает строку s1, состоящую ровно из девяти цифр и обозначающую число, не превосходящее a. Потом второй игрок, видя s1, выписывает строку s2, состоящую ровно из девяти цифр и обозначающую число, не превосходящее b. Здесь a и b — некоторые заданные константы, строки s1 и s2 игроки выбирают сами. Лидирующие нули в строках разрешаются.

Если число, задающееся конкатенацией (склейкой) строк s1 и s2, делится на mod, выигрывает второй игрок. Иначе — выигрывает первый игрок. Даны числа a, b, mod. Требуется определить, кто выиграет при оптимальной игре обоих. Если выиграет первый игрок, также требуется найти лексикографически минимальный выигрышный ход.

Входные данные

В первой строке заданы три целых числа a, b, mod (0 ≤ a, b ≤ 109, 1 ≤ mod ≤ 107).

Выходные данные

Если выиграет первый игрок, выведите «1» и лексикографически минимальную строку, которую ему нужно выписать, чтобы победить. Если выиграет второй игрок, выведите одно число «2».

Примеры
Входные данные
1 10 7
Выходные данные
2
Входные данные
4 0 9
Выходные данные
1 000000001
Примечание

Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка x лексикографически меньше строки y, если существует такое i (1 ≤ i ≤ 9), что xi < yi, а для любого j (1 ≤ j < i) xj = yj. Сравниваемые строки всегда имеют длину 9.