Challenge: Rotate the Carousel

Lab Java Beginner 10 points

A carousel has n seats with numbers in them. It turns k steps to the right: the last item moves to the front, k times. Print the new order. k can be bigger than n, so don't really turn it k times – work out where each item lands.

Input

Line 1: n k. Line 2: n whole numbers.

Output

The rotated numbers, separated by spaces.

Example

Input

5 2
1 2 3 4 5

Output

4 5 1 2 3

Sample input available Sample output available

Editor

Java

Hints

Turning n steps puts everything back where it started, so only k % n matters.

The item at index i moves to index (i + shift) % n.

Solution explanation

Turning one step at a time would be O(n·k). Placing each item directly is O(n).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int shift = (int) (k % n);
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            out[(i + shift) % n] = a[i];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(out[i]);
        }
        System.out.println(sb);
    }
}

Output

Answer