Cô Q hôm nay cho các em sinh viên thực hành về mạng tích chập CNN (Convolutional Neural Network) để giúp các em hiểu rõ cách hoạt động của CNN trong xử lý ảnh.

Cô Q cho các em 1 ảnh có kích thước N X N và kích thước của bộ lọc (Kernel) là K X K. Sau khi bộ lọc quét qua ảnh, ảnh sẽ có kích thước (N - K + 1) x (N - K + 1). Cô Q yêu cầu các em hãy tính ảnh đầu ra sau khi kernel quét qua ảnh. Trong bài toán này, công thức được định nghĩa với pixel có tọa độ (i, j) của ảnh đầu ra như sau:

\[ O_{i,j} = \sum_{u=0}^{K-1} \sum_{v=0}^{K-1} I_{i+u,\,j+v}\,K_{u,v} \]

Yêu cầu: Hãy thực hiện yêu cầu của cô Q.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên N và K.
• N dòng tiếp theo, mỗi dòng gồm N số tự nhiên tương ứng với giá trị của mỗi pixel trên ảnh.
• K dòng tiếp theo, mỗi dòng gồm K số tự nhiên tương ứng với giá trị của từng phần tử trong kernel.

Dữ liệu ra:

• Gồm N-K+1 dòng, mỗi dòng gồm N-K+1 số biểu thị kết quả sau khi chạy lớp kernel.

Input:

4 2
1 2 3 4
5 6 7 8
9 8 7 6
5 4 3 2
1 0
0 -1

Output:

-5 -5 -5
-3 -1  1
 5  5  5

Giải thích:

• O_0,1 = 1x1 + 2x0 + 5x0 + 6x(-1) = 1 - 6 = -5
• O_0,1 = 2×1 + 3×0 + 6×0 + 7×(-1) = 2 - 7 = -5
• O_0,2 = 3×1 + 4×0 + 7×0 + 8×(-1) = 3 - 8 = -5
• O_1,0 = 5×1 + 6×0 + 9×0 + 8×(-1) = 5 - 8 = -3
• O_1,1 = 6×1 + 7×0 + 8×0 + 7×(-1) = 6 - 7 = -1
• O_1,2 = 7×1 + 8×0 + 7×0 + 6×(-1) = 7 - 6 = 1
• O_2,0 = 9×1 + 8×0 + 5×0 + 4×(-1) = 9 - 4 = 5
• O_2,1 = 8×1 + 7×0 + 4×0 + 3×(-1) = 8 - 3 = 5
• O_2,2 = 7×1 + 6×0 + 3×0 + 2×(-1) = 7 - 2 = 5

Giới hạn:

• ~1 \le N, K \le 50, K \le N~.
• Các pixel trong ảnh có giá trị nằm trong khoảng ~[0, 255]~.
• Các phần tử trong kernel có giá trị nằm trong khoảng ~[-2, 2]~.