332. Система счисления

Программист Марат совсем недавно начал изучать информатику в Яндекс Учебнике. Его настолько увлекла тема «Системы счисления», что он всю ночь решал примеры на сложение и вычитание чисел в различных системах счисления. Однако когда на следующий день он снова открыл свои записи, он заметил, что многие записанные им равенства неверны в тех системах счисления, которые были даны в примерах из учебника. «Интересно, а есть ли в принципе какая-то система счисления, в которой это равенство оказалось бы верным?» — огорчённо спрашивал себя Марат, глядя в свою тетрадь с примерами. «А если есть, то какое минимальное у неё может быть основание?» — задумался он.

Помогите Марату ответить на эти вопросы. Для заданного равенства найдите минимальное основание системы счисления, в которой равенство будет верным, или укажите, что такой системы счисления нет.

В единственной строке $s$ задано арифметическое выражение, систему счисления которого необходимо определить ($|s| \le 10^6$).

Строка $s$ состоит из цифр $0$ — $9$, букв латинского алфавита в верхнем регистре $A$ — $Z$, пробелов и символов +, -, =. Пробелы опциональны и не несут смысла, они могут отделять арифметические знаки от чисел.

Гарантируется, что $s$ представляет собой синтаксически корректное выражение, в котором есть ровно один знак = и отсутствуют унарные плюсы и минусы.

Выведите минимальное основание $b$ ($b \geqslant 2$) системы счисления, в которой выражение обращается в верное равенство. Если такого $b$ нет, выведите $-1$.

• В первом примере минимальная система, в которой выражение имеет смысл — троичная, но слева $2 + 2 = 11$, а справа $11 - 1 = 10$ и выражение не обращается в верное равенство. В четверичной же $2 + 2 = 10$ и выражение обращается в верное равенство.

• Во втором примере выражение обращается в верное равенство во всех системах, начиная с двоичной, поэтому ответ $2$.

• В третьем примере невозможно найти системы счисления, в которой бы $2 = 3$, поэтому ответ $-1$.

• В четвёртом примере минимальная система, в которой выражение имеет смысл — двенадцатеричная, в ней же выражение обращается в верное равенство.