Giá trị nhỏ nhất trong $m$ vị trí trước (Minimum in Previous m Positions)

Nguồn: Luogu

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

Đề bài

Cho dãy $a_1,a_2,\ldots,a_n$. Với mỗi vị trí $i$, cần tìm giá trị nhỏ nhất trong tối đa $m$ phần tử đứng ngay trước $a_i$. Nếu trước $a_i$ chưa có phần tử nào thì kết quả là $0$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ số nguyên dương $a_i$.

Output

In $n$ dòng; dòng thứ $i$ là kết quả ứng với vị trí $i$.

Subtask

• Subtask 1 (20%): $1 \le m \le n \le 2000$.
• Subtask 2 (30%): $1 \le m \le n \le 2\cdot 10^5$.
• Subtask 3 (50%): $1 \le m \le n \le 2\cdot 10^6$.

Toàn bộ dữ liệu tuân theo: $1 \le m \le n \le 2\cdot10^6$, $1 \le a_i \le 3\cdot10^7$.

Ví dụ

Input

6 2
7 8 1 4 3 2

Output

0
7
7
1
1
3

Giải thích

Vị trí đầu tiên không có phần tử đứng trước nên in $0$. Từ vị trí thứ hai trở đi chỉ xét tối đa hai phần tử ngay trước.