Реконструкція танцю
Sьогодні ми розглянемо, як відновити розташування стрілок на танцювальному майданчику, використовуючи дані з двох моментів часу. Уявімо, що у нас є N танцюристів, розташованих у колі, і кожен з них має стрілку, яка вказує на наступного партнера. Ми знаємо, що за K тактів кожен з них перемістився з однієї позиції на іншу.
На початку у нас є певне розташування, яке ми позначаємо як a, і ми хочемо дізнатися, як виглядає це розташування після K переміщень. Наше завдання - визначити, як виглядає початкове розташування, якщо ми знаємо, що після K переміщень ми отримали певний порядок.
Вхідні дані
- Перше число - це кількість людей N (2 ≤ N ≤ 10000). - Друге число - кількість переміщень K (1 ≤ K ≤ 1000000000). - Наступні N чисел - це перестановка чисел від 1 до N, яка показує, як виглядає кінцеве розташування після K переміщень.
Вихідні дані
- Якщо існує таке початкове розташування, яке після K переміщень дає заданий порядок, виведіть його. Інакше виведіть "Impossible".
Ваше завдання - визначити, чи можна так розташувати танцюристів, щоб після K переміщень вони опинилися у заданих позиціях. Якщо це можливо, знайдіть таке розташування. Якщо ні, вкажіть, що це неможливо.