Remote Training on Programming

Когда один известный алгебраист (далее — О. И. А.) с мат-меха был маленьким, ему в школе строго-настрого запретили брать квадратные корни из отрицательных чисел. Конечно же, О. И. А. на запрет наплевал и даже (о, ужас!) стал использовать то, что получается после взятия такого корня, в качестве основания системы счисления.

Недавно О. И. А. нашёл свои старые записи, а в них какое-то подозрительное тождество. Чтобы проверить его справедливость, О. И. А. достаточно сложить два числа и посмотреть на результат. Но, к сожалению, эти два числа записаны как раз в системе счисления с основанием, равным корню из отрицательного числа (а конкретно, ), и ответ тоже должен быть представлен в системе счисления с основанием . Ваша задача — помочь О. И. А. проверить тождество, сложив два числа.

Как известно, мнимые числа — это как раз те числа, которые получаются в результате взятия квадратного корня из отрицательного числа. В системе с мнимым основанием в числах используются цифры от 0 до k-1, включительно. Мнимые основания систем счисления ведут себя так же, как обычные, то есть число, записанное как d_3d2d1d0, вычисляется по формуле d₃·b³+d₂·b²+d₁·b+d₀, где b — основание системы счисления (в этой задаче оно равно ). Таким образом могут получаться числа вида , где x и y — любые целые цисла. Например: .

Несмотря на то, что операция взятия корня из отрицательного числа неоднозначна (как , так и дают в квадрате -4), в качестве основания системы счисления всегда берётся одно и то же число.