Під час своєї роботи алгоритм стискання даних методом "сортування блоку" застосовує до блоків даних перетворення, яке визначається наступним чином.
Рядок P
називається ротацією рядка S
, якщо він утворений циклічним зсувом символів S
, тобто якщо S=a[1]a[2]…a[N]
, де a[i]
— i
–ий символ рядка S
, то P = a[p]a[p+1]…a[N]a[1]…a[p-1]
, де 1 ≤ p ≤ N
. Розглянемо таблицю M
розміру N
×N
, рядками якої є всі ротації рядка S
, відсортовані у лексикографічному (словниковому) порядку за зростанням.
Нехай рядок L
є останнім стовпчиком таблиці M
. Пряме перетворення отримує на вхід рядок S
, видає рядок L
та число K
— номер рядка таблиці M
, що містить рядок S
. (Якщо таких рядків декілька, видається номер будь–якого з них).
Для S = 'abraka'
таблицю M
зображено на малюнку. Рядок S
знаходиться у другому рядку таблиці M
, L = 'karaab'
.
Напишіть програму, що виконує зворотнє перетворення, тобто отримує на вхід рядок L
і число K
, та видає рядок S
.
Перший рядок вхідного файлу містить два цілих числа: K
та N
, 1 ≤ N ≤ 30000
, 1 ≤ K ≤ N
. Другий рядок містить N
символів рядка L
— маленьких латинських літер.
Єдиний рядок вихідного файлу повинен містити рядок S
.