G. A + B = C
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В поисках вдохновения для задач Слава отправился шерстить просторы интернета — и нашёл интересную загадку.

Загадка имела вид $$$A + B = C$$$, где цифры чисел $$$A$$$, $$$B$$$ и $$$C$$$ были заменены на буквы латинского (либо иного) алфавита.

Причем действовали три дополнительных правила:

  • числа в исходном тождестве не имеют ведущих нулей и не равны нулю.
  • каждой букве соответствует ровно одна заменяемая цифра.
  • каждой цифре соответствует ровно одна заменяющая буква.

Решением такого рода загадок является любая подстановка «буква — цифра», превращающая запись в тождество.

Для данной загадки описанного выше вида вам необходимо

  • вычислить количество решений данной загадки.
  • если существует хотя бы одно решение, то вывести любое из них.
Входные данные

В первой строке дана строка $$$SA$$$ $$$(1 \le |SA| \le 3)$$$ — строка, соответствующая числу $$$A$$$ в загадке.

Во второй строке дана строка $$$SB$$$ $$$(1 \le |SB| \le 3)$$$ — строка, соответствующая числу $$$B$$$ в загадке.

В третьей строке дана строка $$$SC$$$ $$$(1 \le |SC| \le 4)$$$ — строка, соответствующая числу $$$C$$$ в загадке.

Гарантируется, что строки $$$SA$$$, $$$SB$$$ и $$$SC$$$ состоят только из букв латинского алфавита в верхнем регистре.

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

В первой строке выведите целое число $$$R$$$ $$$(0 \le R \le 10^9)$$$ — количество решений данной загадки.

Если $$$R \gt 0$$$, то в следующих трёх строках выведите любое из решений загадки:

  • число $$$A$$$, загаданное строкой $$$SA$$$;
  • число $$$B$$$, загаданное строкой $$$SB$$$;
  • число $$$C$$$, загаданное строкой $$$SC$$$.
Примеры
Входные данные
ABC
DEF
AAAZ
Выходные данные
72
123
987
1110
Входные данные
AAA
BBB
CDC
Выходные данные
0
Входные данные
PQ
ST
PV
Выходные данные
0
Входные данные
X
Y
X
Выходные данные
0
Примечание

Первый тестовый пример

Загадка ABC + DEF = AAAZ может быть решена, например, как $$$123 + 987 = 1110$$$:

  • $$$A$$$ соответствует $$$1$$$;
  • $$$B$$$ соответствует $$$2$$$;
  • $$$C$$$ соответствует $$$3$$$;
  • $$$D$$$ соответствует $$$9$$$;
  • $$$E$$$ соответствует $$$8$$$;
  • $$$F$$$ соответствует $$$7$$$;
  • $$$Z$$$ соответствует $$$0$$$.

Примеры других возможных решений:

  • $$$147 + 963 = 1110$$$;
  • $$$167 + 948 = 1115$$$.

Второй тестовый пример

Загадка AAA + BBB = CDC не имеет решений, так как в этом случае

  • либо одной и той же цифре соответствуют две буквы $$$C$$$ и $$$D$$$;
  • либо одной и той же букве ($$$A$$$ либо $$$B$$$) соответствуют хотя бы две различные цифры.

Третий тестовый пример

Загадка PQ + ST = PV не имеет решений, так как в этом случае в числе, загаданном как ST, должен быть ведущий ноль, что недопустимо.

Четвёртый тестовый пример

Загадка X + Y = X не имеет решений, так как в этом случае число, загаданное как Y, должно равняться нулю, что недопустимо.