A display board shows n numbers. Rotate them k steps to the right (the last element moves to the front each step), in place with O(1) extra memory, and print the result. k can be larger than n.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ k ≤ 10^9
Input and output
- Input
- Line 1: n and k. Line 2: n integers.
- Output
- The rotated array on one line.
Examples
Input 1
5 2
1 2 3 4 5Output
4 5 1 2 3Two steps right: 4 5 1 2 3.
Input 2
3 7
10 20 30Output
30 10 207 mod 3 = 1 step: 30 10 20.
Show hints
- Rotating by k is the same as rotating by k mod n.
- Reverse the whole array, then reverse the first k elements and the remaining n − k separately.
Show the explanation
First reduce k = k % n. The three-reversal trick then does the rotation in place: reverse the whole array, reverse the first k elements, and reverse the last n − k. For 1 2 3 4 5 with k = 2: reverse → 5 4 3 2 1, fix the first two → 4 5 3 2 1, fix the rest → 4 5 1 2 3. Each element moves a constant number of times, so it is O(n) time and O(1) space. Copying into a new array is the easy O(n)-space version.
Original UniCircle question. Last reviewed 22 Oct 2026.