游戏工程师小明购买了VR设备之后爱上了体感游戏，而最近他把他的业余时间花在了一款叫十字斩的游戏里。当你戴上VR眼镜启动游戏后，先选择一首音乐，然后会发现有一个N*N的方阵呈现在你的眼前，方阵的每个格子上都有一个数字。然后伴随着音乐节拍，你需要按照时机对方阵进行一次十字斩击（同时斩掉一行和一列，而且选好了行列后不能斩到选定行列之外的格子）。斩击完了之后，矩阵会收缩成一个（N-1）*（N-1）的方阵。
特别的，若该次十字斩斩到的格子数字和是本次所有十字可能里最大的，则会获得一个Perfect，如果N次十字斩都是Perfect，则可以获得FullCombo的成就。但小明的心算能力不行，至今还未能获得FullCombo的成就。所幸初始数字方阵与音乐是一一对应的，所以小明可以通过预先计算十字斩的位置然后背下来，游玩的时候根据记忆去进行十字斩位置的选择即可。
小明上了一天班已经不想写代码了，所以他拜托你来写一个程序为他计算出十字斩的方案。
每个输入数据包含一个测试点。
第一行为一个正整数N，方阵的大小。0 < N <= 500
接下来N行，每行有N个数字，第i行第j个数字表示方阵i行j列上的数字是多少，对于每个数字，保证是非负整数且范围在[0, 65535]内。
输出N行，每行两个整数n，m，第i行的n，m表示第i次斩击时，斩击第n行和第m列的数字和是最大的。注意如果此时有多种方案，输出n最小的（更小的数字更方便小明记忆），如果还有多种方案，输出m最小的。
而且n、m的坐标是对于当前的（N + 1 – i）大小方阵而言，并不是对于一开始N*N大小的方阵而言，更加详细的说明参见下方样例说明。
3 1 0 0 0 10 10 0 10 10
2 2 1 2 1 1
对于第一轮，我们斩击2行2列、2行3列、3行2列、3行3列的数字和都是最大的为30（行列重复的那个格子的数字并不会被计算两次），但因为希望n和m都最小，所以我们的斩击选择为2 2
斩击之后剩余的上下左右四个矩阵收缩为新的矩阵
1 0
0 10
此时最优的斩击选择就是1 2 (注意是新方阵下的坐标，而非原方阵的第1行3列)
然后剩下一个1*1的方阵，只有唯一的斩击选择1 1了
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
