Âm thanh của sự im lặng (The Sound of Silence)

Nguồn: Kattis

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

Đề bài

Một bản ghi âm gồm $n$ mẫu $a_i$. Một đoạn dài $m$ mẫu được xem là im lặng nếu hiệu giữa mẫu lớn nhất và nhỏ nhất trong đoạn không vượt quá $c$. Hãy liệt kê mọi vị trí bắt đầu của đoạn im lặng.

Input

Dòng đầu chứa $n,m,c$. Dòng thứ hai chứa $n$ mẫu $a_i$.

Output

In mỗi vị trí bắt đầu hợp lệ trên một dòng theo thứ tự tăng dần. Nếu không có vị trí nào, in NONE.

Subtask

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

Toàn bộ dữ liệu tuân theo: $1 \le n \le 10^6$, $1 \le m \le 10^4$, $0 \le c \le 10^4$, $0 \le a_i \le 10^6$.

Ví dụ

Input

7 2 0
0 1 1 2 3 2 2

Output

2
6

Giải thích

Với $m=2,c=0$, chỉ các cặp bắt đầu tại vị trí $2$ và $6$ có hai giá trị bằng nhau, nên chênh lệch bằng $0$.