← 返回题目列表

Codeforces · 263/E

E. 菱形

中文机器翻译题面 查看原题

你有一个大小为 n × m 的表。在第 i 行 (1 ≤ i ≤ n) 和第 j 列 (1 ≤ j ≤ m) 的交点上有一个非负整数 ai, j。此外,你还有一个非负整数 k。

你的任务是找到满足以下条件的整数对 (a, b):

- k ≤ a ≤ n - k + 1;
- k ≤ b ≤ m - k + 1;
- 让我们表示满足不等式的所有整数 x 和 y 中函数 $$f(x,y) = \sum_{i=1}^{n} \sum_{j=1}^{m} a_{i,j} \cdot max(0,k-|i-x|-|j-y|)$$ 的最大值k ≤ x ≤ n - k + 1和k ≤ y ≤ m - k + 1,作为mval;对于所需的数字对,以下方程必须满足 f(a, b) = mval。

输入

第一行包含三个空格分隔的整数 n、m 和 k (1 ≤ n, m ≤ 1000, $$1 \leq k \leq \left\lfloor \frac{\min(n,m)+1}{2} \right\rfloor$$)。接下来的 n 行每行包含 m 个整数:第 i 行上的第 j 个数字等于 ai, j (0 ≤ ai, j ≤ 106)。

行中的数字以空格分隔。

输出

打印所需的一对整数 a 和 b。用空格分隔数字。

如果有多个正确答案,您可以打印其中任何一个。

示例

输入 #1

4 4 2
1 2 3 4
1 1 1 1
2 2 2 2
4 3 2 1

输出 #1

3 2

输入 #2

5 7 3
8 2 3 4 2 3 3
3 4 6 2 3 4 6
8 7 6 8 4 5 7
1 2 3 2 1 3 2
4 5 3 2 1 2 1

输出 #2

3 3