В одной очень древней стране была популярна следующая игра. В игру играет два человека. Сначала первый игрок выписывает строку s1, состоящую ровно из девяти цифр и обозначающую число, не превосходящее a. Потом второй игрок, видя s1, выписывает строку s2, состоящую ровно из девяти цифр и обозначающую число, не превосходящее b. Здесь a и b — некоторые заданные константы, строки s1 и s2 игроки выбирают сами. Лидирующие нули в строках разрешаются.
Если число, задающееся конкатенацией (склейкой) строк s1 и s2, делится на mod, выигрывает второй игрок. Иначе — выигрывает первый игрок. Даны числа a, b, mod. Требуется определить, кто выиграет при оптимальной игре обоих. Если выиграет первый игрок, также требуется найти лексикографически минимальный выигрышный ход.
Выходные данные
Если выиграет первый игрок, выведите «1» и лексикографически минимальную строку, которую ему нужно выписать, чтобы победить. Если выиграет второй игрок, выведите одно число «2».
Примечание
Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка x лексикографически меньше строки y, если существует такое i (1 ≤ i ≤ 9), что xi < yi, а для любого j (1 ≤ j < i) xj = yj. Сравниваемые строки всегда имеют длину 9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 10 7
|
2
|
|
2
|
4 0 9
|
1 000000001
|