Cho dãy hoán vị ~P~ gồm ~N~ phần tử. Hãy tính các giá trị hàm ~\mathrm{F}(i)~ thuộc một trong hai loại sau với mọi ~1 \le i \le N~:

• Loại ~1~: ~\mathrm{F}(i) = \displaystyle \min_{j \neq i} \{(P_i-P_j) + (i-j)\}~
• Loại ~2~: ~\mathrm{F}(i) = \displaystyle \min_{j \neq i} \{|P_i-P_j| + |i-j|\}~

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~f~, với ~f \in \{1,2\}~ cho biết hàm ~\mathrm{F}(i)~ thuộc loại ~f~.
• Dòng thứ hai chứa ~N~ số nguyên của dãy ~P~ ~(~~1 \le P_i \le N~~)~.
• Dữ liệu đảm bảo dãy ~P~ là một dãy hoán vị hợp lệ.

Output

• In ra trên một dòng là các giá trị hàm ~\mathrm{F}(i)~ theo thứ tự tăng dần chỉ số ~i~, cách nhau bởi khoảng trắng.

Examples

Sample Input 1

4 1
2 3 1 4

Sample Output 1

-5 -3 -4 3

Sample Input 2

4 2
2 3 1 4

Sample Output 2

2 2 3 3

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~2 \le N \le 1000~ và ~f \in \{1,2\}~
• Subtask ~2~ với ~30\%~ số điểm: ~2 \le N \le 2.10^5~ và ~f=1~
• Subtask ~3~ với ~40\%~ số điểm: ~2 \le N \le 2.10^5~ và ~f=2~

Notes

Trong ví dụ ~2~, với ~i=1~:

• Với ~j=2~: ~|P_1-P_2| + |1-2|=2~
• Với ~j=3~: ~|P_1-P_3| + |1-3|=3~
• Với ~j=4~: ~|P_1-P_4| + |1-4|=5~

Vì vậy, ~\mathrm{F}(1)=\min\{2,3,5\}=2~