Быстрое возведение в степень
Очень часто возникает задача эффективного вычисления x^n по данным x и n, где n - положительное целое число.
Предположим, например, что необходимо вычислить x^16. Можно просто начать с x и 15 раз умножить его на x. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя x^2, x^4, x^8, x^16.
Эта же идея, в целом, применима к любому значению n следующим образом. Запишем n в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1" парой символов SX, а каждый "0" - символом S и вычеркнем крайнюю слева пару символов "SX". Результат представляет собой правило вычисления x^n, в котором "S" трактуется как операция возведения в квадрат, а "X" - как операция умножения на x. Например, n = 23 имеет двоичное представление 10111. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и умножить на x", т.е. последовательно вычислить значения x^2, x^4, x^5, x^10, x^11, x^22, x^23.
Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа x в степень x^n
Входные данные
Одно натуральное число n, не превышающее 2·10^9.
Выходные данные
Выведите строку для правила возведения числа x в степень n для получения x^n.