Vườn hoa hướng dương của Kazami Yuuka có thể được biểu diễn bằng một ma trận $n\times n$ trong đó mỗi ô $(i,j)$ chứa một số nguyên dương là độ đẹp của bông hoa ở ô $(i,j)$.

Yuuka mượn được của Kawashiro một chiếc máy hái hoa có bán kính $k$, nói cách khác nếu sử dụng máy ở vị trí $(i,j)$ thì có thể hái được những bông hoa ở vị trí $(x,y)$ nếu $|i-x|+|j-y|\le k$.

Muốn hái được những bông hoa đẹp nhất, cô nhờ các bạn, với mỗi vị trí của vườn hoa tính tổng độ đẹp những bông hoa hái được nếu sử dụng máy ở vị trí đó.

Input:

• Dòng đầu tiên gồm số nguyên dương $n$ và $k$ ($1\le k\le n\le 1000$).
• $n$ dòng tiếp theo mỗi dòng gồm $n$ số nguyên không âm là độ đẹp của bông hoa, giá trị không vượt quá ${10}^9$.

Output:

• In ra ma trận $n\times n$ tương ứng

Sample Test

Input 1:

5 2
1 2 3 5 2
3 4 3 2 9
3 4 1 1 3
1 9 4 3 2
7 5 6 3 4

Output 1:

16 25 23 27 24 
21 35 41 36 27 
33 40 46 40 27 
36 47 42 38 29 
31 39 42 28 21 

Input 2:

3 1
1 0 2
0 0 1
1 0 0

Output 2:

1 3 3 
2 1 3 
1 1 1