B. Noisy Cat
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Một ngày nọ, một bức ảnh đen trắng của chú mèo dễ thương bị lỗi trong quá trình truyền dẫn và gây ra nhiễu. Bức ảnh được biểu diễn bởi ma trận $$$n \times m$$$, mỗi phần tử là một giá trị nguyên từ $$$0$$$ đến $$$10^9$$$, tương ứng với độ sáng của một pixel ($$$0$$$ là đen hoàn toàn, $$$10^9$$$ là trắng hoàn toàn).

Nhiệm vụ của bạn là giúp ảnh của chú mèo trở lại xinh đẹp như ban đầu bằng cách áp dụng bộ lọc trung vị (median filter) kích thước $$$k \times k$$$. Cụ thể, với mỗi vùng $$$k \times k$$$, bạn sẽ thay thế giá trị của ô trung tâm với trung vị của $$$k^2$$$ pixel trong vùng đó.

Lưu ý, bộ lọc trung vị sẽ được áp dụng đồng thời cho mọi pixel.

Giá trị trung vị của một dãy có số phần tử lẻ là số nằm chính giữa dãy đó sau khi đã sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy [$$$1, 5, 2, 3, 5$$$] là $$$3$$$.

Các pixel khác (không đủ khung $$$k \times k$$$) sẽ giữ nguyên.

Input

Dòng đầu tiên gồm một số nguyên $$$t$$$ ($$$1 \le t \le 1000$$$) — số testcase, mô tả của mỗi testcase như sau.

Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$m$$$ và $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le \mathrm{min}(n, m)$$$, $$$k$$$ là một số lẻ) — số hàng, số cột và kích thước cạnh của bộ lọc trung vị.

$$$n$$$ dòng tiếp theo của mỗi testcase gồm $$$m$$$ số nguyên $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$0 \le a_{ij} \le 10^9$$$) — độ sáng của mỗi pixel.

Dữ liệu vào bảo đảm tổng $$$n \times m \le 2 \cdot 10^5$$$ trong mọi testcases.

Output

Với mỗi testcase, in ra $$$n$$$ dòng, mỗi dòng có $$$m$$$ ký tự cho biết độ sáng của mỗi pixel sau khi đã lọc trung vị.

Example
Input
3
3 3 3
20 30 25
40 255 35
22 28 26
4 5 3
83 3 75 32 42
32 16 3 50 29
86 6 73 32 77
3 83 16 42 50
1 1 1
10
Output
20 30 25
40 28 35
22 28 26
83 3 75 32 42
32 32 32 42 29
86 16 32 42 77
3 83 16 42 50
10
Note

Ở ví dụ thứ nhất, chỉ có một ô sẽ được áp dụng bộ lọc, nằm tại vị trí ($$$2, 2$$$). Chọn ra các ô trong vùng $$$3 \times 3$$$ ta có: dãy [$$$20, 22, 25, 26, 28, 30, 35, 40, 255$$$], thay thế giá trị của ô ($$$2, 2$$$) từ $$$255$$$ thành $$$28$$$. Các ô còn lại giữ nguyên.