1. Сновида

Максимальна оцінка: 13 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: sleep.in
Вихідний файл: sleep.out
Програма: sleep.*

У президента Першого нацiонального банку майора Томаса Б. Кiнгмена (героя оповiдання О'Генрi "Товаришi iз Сан-Розарiо") з'явилася шкідлива звичка щоночi перекладати однаковим чином вмiст сейфiв, у яких клiєнти зберiгають свої коштовностi.

Завдання
Створiть програму, яка допоможе вирахувати, через скiльки дiб всi коштовностi вперше повернуться на свої мiсця.

Вхідні дані
Перший рядок вхiдного файлу мiстить одне натуральне число n — кiлькiсть сейфiв банку, що неперевищує 15500. Далi (починаючи з другого рядка) файл мiстить послiдовнiсть n рiзних натуральних чисел в межах вiд 1 до n включно. k-ий член цiєї послiдовностi — номер сейфу, куди майор перекладає вмiст k-го сейфу першої ночi.

Вихідні дані
Єдиний рядок вихiдного файлу має мiстити запис у десятковiй системi числення шуканого числа дiб, що містить не більше, ніж 1000 цифр.

Приклад

2. Корiнь квадратний

Максимальна оцінка: 34 бали
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: root.in
Вихідний файл: root.out
Програма: root.*

Щоб добути квадратний корiнь з десяткового дробу (наприклад, 65432.109), його запис розбивають праворуч i лiворуч вiд десяткової крапки на гранi, що мiстять по 2 цифри. У крайнiй лiвiй гранi може виявитися i одна цифра (6). Перша цифра кореня (2) знаходиться як найбiльша з усiх тих цифр, квадрати яких не перевищують першої гранi (6). Потiм вiд першої гранi вiднiмають квадрат першої цифри кореня (4), i до рiзницi приписують праворуч (зносять) наступну грань (54). Лiворуч вiд отриманого числа (254) пишуть подвоєну першу цифру кореня (4), а за наступну цифру (5) беруть найбiльшу з тих, добуток яких на число, утворене приписуванням її до подвоєної першої цифри праворуч, (45 ∙ 5=225) не перевищує результату приписування до попередньої рiзницi вiдповiдної гранi (254). Цю цифру (5) записують пiсля першої цифри кореня i т.д. Десяткова крапка у коренi ставиться тодi, коли зноситься перша грань праворуч вiд десяткової крапки числа.

Завдання
Створiть програму root.*, яка вираховує корiнь квадратний додатного десяткового дробу.

Вхідні дані
Єдиний рядок вхiдного файлу root.in мiстить у вказаному порядку скiнченний або перiодичний додатний десятковий дрiб (всього — до 1000 символiв разом з десятковою крапкою) a та натуральне число n, яке не перевищує 100.

Вихідні дані
Єдиний рядок файлу root.out має мiстити подання кореня квадратного а скiнченним чи перiодичним десятковим дробом, якщо це можливо, iнакше — корiнь квадратний числа a з недостачею з точнiстю до n цифр пiсля десяткової крапки.

Приклади