Циклический сдвиг

Циклически сдвиньте массив из $n$ чисел на $k$ шагов вправо: на каждом шаге последний элемент переходит в начало, остальные сдвигаются на одну позицию вправо. Например, 1 2 3 за один шаг становится 3 1 2.

В первой строке $n$ и $k$ ($1 \le n \le 10^5$, $0 \le k \le 10^9$). Во второй — $n$ целых чисел ($|a_i| \le 10^9$).

В одной строке $n$ чисел — сдвинутый массив.

Сдвиг на $n$ шагов возвращает массив в исходное состояние, поэтому вместо $k$ достаточно $k \bmod n$ — выполнить $10^9$ шагов по одному не хватит времени. Элемент попадает в новом массиве на место . Во втором примере : .