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

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên $a_0,a_1,\ldots,a_{n-1}$ và số nguyên không âm $d$. Chuẩn hóa

Sau khi dịch vòng phải $r$ bước, mảng kết quả $b$ thỏa

Hãy tạo $b$ bằng mảng phụ và in kết quả. Công thức có thêm $n$ để chỉ số trước phép modulo không âm.

Input

Dòng đầu chứa $n$ và $d$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In mảng sau khi dịch vòng phải $d$ bước.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $0\le d\le10^3$, $|a_i|\le10^3$.

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

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

Ví dụ

Input

6 8
10 20 30 40 50 60

Output

50 60 10 20 30 40

Giải thích

$r=8\bmod6=2$, nên hai phần tử cuối chuyển lên đầu theo đúng thứ tự.