Left Rotate by d Using an Auxiliary Array (Dịch vòng trái d bước bằng mảng phụ)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$ and a non-negative integer $d$, normalize

After a left rotation by $r$ positions,

Construct $b$ using an auxiliary array and print it. The value $d$ may be much larger than $n$.

Input

The first line contains $n$ and $d$. The second line contains $n$ integers $a_i$.

Output

Print the array after the left rotation.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $0\le d\le10^3$, $|a_i|\le10^3$.

Subtask 2 (30 points): $1\le n\le5000$, $0\le d\le10^{12}$, $|a_i|\le10^6$.

Subtask 3 (50 points): $1\le n\le2\cdot10^5$, $0\le d\le10^{18}$, $|a_i|\le10^9$.

Example

Input

7 9
1 2 3 4 5 6 7

Output

3 4 5 6 7 1 2

Explanation

The sample follows the mathematical definition above.