Швидке піднесення до степеня
Дуже часто постає задача ефективного обчислення 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 до степені x^n.