在一个神奇的世界里，有一个被称为 AC 的公园，拥有着奇妙的魔法力量。公园的土地是一个 N \times N 的网格，有东西向的行和南北向的列。每个网格的高度都是由神秘的魔法所决定的，用 A_{i,j} 表示从北边数起第 i 行、从西边数起第 j 列的正方形的高度。

Piggy 是一位年轻的魔法师，决定在 AC 公园内创造一个神奇的魔法池塘，池塘的面积是一个 K \times K 的正方形，其中 K 是一个正整数。他希望这个池塘能够成为公园中最神奇的地方，吸引更多的魔法师前来探险。

Piggy 想要在公园内选择一个面积为 K \times K 的矩形区域，并且该区域内所有正方形的高度的中位数最小。

如果边长是 K 的正方形，内部的元素个数就是 K \times K。中位数是指的是这 K \times K 个数，按照从大到小排序后，第 {\lfloor \frac{K^2}{2} \rfloor + 1} 个数。

现在，你需要帮助 Piggy 计算所有可能的 K \times K 区域中，正方形高度中位数的最小值。只有在找到了这个最小的中位数之后，Piggy 才能开始创造池塘，让公园变得更加有趣。

第一行两个整数，分别代表公园的边长 N , 选择区域的边长 K。

下面的 N 行，N 列，表示每一块小正方形的高度 A_{i,j}。

按题意，输出 K \times K 区域内的最小中位数。

【数据范围】

对于 20\% 的数据，1 \le N \le 50。

对于 40\% 的数据，1 \le N \le 400。

对于 100\% 的数据，1 \leq K \leq N \leq 800，0 \leq A_{i,j} \leq 10^9。

输入中的所有值都是整数。

【样例 1 解释】

N = 3 ，K = 2。

1 7 0
5 8 11
10 4 2

所选择正方形数列可能为：

1,7,5,8、7,0,8,11、5,8,10,4、8,11,4,2 ,最小的中位数为 4 。

【样例 2 解释】

1,2,3,4,5,6,7,8,9 中位数是 5 。

前缀和月赛二分答案