Задача №3578. Сдвиг
Петя и Вася придумали систему шифровки для обмена записками. Суть ее заключается в следующем. Дана исходная строка S. S' — циклический сдвиг строки влево (первый символ становится последним, а остальные перемещаются на одну позицию влево), S" — циклический сдвиг строки S' и т.д. Петя с Васей выписывают на листок бесконечную последовательность символов SS'S"S"'.... Если им необходимо зашифровать символ C, то они ищут какое-либо вхождение этого символа в выписанную последовательность и записывают его порядковый номер k. Нумерацию символов они ведут с единицы.
Злоумышленник Коля перехватил сообщение и выкрал исходную строку S. Однако он не может определить, какой символ стоит в последовательности SS'S"S"'... на k-ом месте. Помогите злоумышленнику Коле узнать, какой символ соответствует числу k.
Первая строка входного файла содержит строку, состоящую только из строчных латинских букв. Длина строки не превышает 100000 символов. Вторая строка входного файла содержит единственное целое число 1 ≤ k ≤ 2 × 109.
Единственная строка выходного файла должна содержать символ, который окажется на k-ом месте сформированной строки.
abcd 5
b
abcd 17
a