Dịch vòng trái d bước bằng mảng phụ (Left 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$. Trước hết chuẩn hóa

Sau khi dịch vòng trái $r$ bước, phần tử ở vị trí $i$ của mảng kết quả $b$ là

Hãy tạo $b$ bằng một mảng phụ và in kết quả. Giá trị $d$ có thể lớn hơn nhiều so với $n$.

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 trá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

7 9
1 2 3 4 5 6 7

Output

3 4 5 6 7 1 2

Giải thích

$r=9\bmod7=2$, nên phần tử đầu tiên của kết quả là $a_2=3$.