题目：
背景
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是JoyOI今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去JoyOI七夕祭游玩。
描述
JoyOI七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的JoyOI开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
输入格式
第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。
输出格式
首先输出一个字符串。如果能满足Vani的全部两个要求，输出both；如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；如果只能使各列中cl感兴趣的摊点数一样多，输出column；如果均不能满足，输出impossible。
如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
样例输入1
2 3 4
1 3
2 1
2 2
2 3
样例输入2
3 3 3
1 3
2 2
2 3
样例输出1
row 1
样例输出2
both 2
解析：
这道题就类似于均分纸牌的问题：一行n个人，给你每个人有的纸牌数，每个人可以向他旁边的人递纸牌，每次递1张，最少需要递送多少次能使全部人拥有同样多的纸牌。
解法就是：就是每次只考虑满足一个人，从头开始，每个人从下一个人处拿或者给纸牌直到这个人的牌数等于平均值（不用管下一个人是正是负）
设第i个人拥有的纸牌为a【i】，算出最终每个人平均的纸牌数为flag，令每一个a【i】减去flag，计算a的前缀和sum[i]，最后将sum的绝对值都加起来就是答案。
虽然可以直接强行计算每一个a【i】-flag 的绝对值再加起来，但是对于另外的题来说这种做法就不太方便了。
对于本题来说，每一行的之间的交换不会影响列，每一列的交换同理，因此可以将行和列单独的分开操作，那么就只考虑行的情况。
首先我们考虑两种摊位摆放情况，看看是否一样。
第一种情况会不会相互挡住呢？因为假如需要向上交换那么一定是上面那一排向上交换，交换之后就没有东西挡住下面那一行了，向下交换也是一样，因此这两种情况操作起来都是一样的。
那么就可以转化问题了：设行数为n，摊位数为k，给你每一行的摊位数，问至少操作几次可以将摊位均分，对于某一行的操作可以是该行向上或者向下交换一个摊位。
首先很明显，可以均分的条件是n%k==0，
然后此题就很类似于纸牌均分的问题，唯一的不同就是此题是一个环，首先我们就将行看成点，因为没有特定的起点，我们需要找到一个特定的起点将问题转化为纸牌均分问题。
假如存在两个点，他们之间不需要交换摊位，那么就可以将这两点中间拆开，将环变成线。事实上在环中一定会存在这样的情况，那么如何证明呢？
我们利用反证法，假设存在这样一个环两两之间都需要交换摊位才能平衡，随便选择一个点作为开头，由于交换的方法直接从下一个点拿或者给摊位使得该点的摊位等于平均值，而按照假设这个点的前一个点一定又会与它发生摊位交换，因此该点不等于平均值，与条件不符，假设不成立。
所以环中每两个点都可以做到不交换摊位，取决的是你交换摊位的方法。
我们假设第x个点之后分割环变成线可以取得最优解，设i点的摊位数为a[i]，最终摊位的平均值为flag，我们先将每个a[i]减去平均值flag，然后求a[i]的前缀和为s[i]，那么对于从x开始的情况就有：
根据答案=每一个前缀和的绝对值之和，又因为s[n]=0（每个a都减去flag，最后肯定平衡啊），所以我们可以得出
问题转化到这里就很简单了，最后就是求这个ans的式子的最小值。
最后这个式子就相当于将每一个s【i】铺在数轴上，然后找到一个点i使得点i到每一点的距离之和最小。
先考虑s[1] 和 s[n]这两点，很明显当点位于s[i]和s[n]之间时到这两点的距离之和最短，恒等于abs(s[n]-s[1])
接着考虑s[2]和s[n-1]，同理。
最后就直到当n为奇数的时候，i=(n+1)/2这个点是最优解，当n为偶数的时候，i=n/2 或者 i=n/2 +1 这两点都是最优解。
所以我们只需要将s排序然后找中间那个点，按着式子计算就好了
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
ll hang[maxn], lie[maxn];
int main() {
int *now;
int n, m, t; cin >> n >> m >> t;
ll flag1 = 1LL*t / n, flag2 = 1LL*t / m;
for (register int i = 1; i <= t; i++) {
int inp1, inp2;
scanf("%d %d", &inp1, &inp2);
hang[inp1]++;
lie[inp2]++;
}
for (register int i = 1; i <= n; i++) { // 减去平均值再求前缀和
hang[i] -= flag1;
hang[i] += hang[i - 1];
}
for (register int i = 1; i <= m; i++) {
lie[i] -= flag2;
lie[i] += lie[i - 1];
}
sort(hang + 1, hang + n + 1); //排序找中间数
sort(lie + 1, lie + m + 1);
ll ans = 0;
int xixi;
if (t%n == 0) { //对行解答
xixi = (n+1) /2;
for (register int i = 1; i <= n; i++) {
ans += abs(hang[i] - hang[xixi]);
}
}
if (t%m == 0) { //对列解答
xixi = (m+1) /2;
for (register int i = 1; i <= m; i++) {
ans += abs(lie[i] - lie[xixi]);
}
}
if (t%n == 0 && t%m != 0) {
printf("row ");
}
else if (t%m == 0 && t%n != 0) {
printf("column ");
}
else if (t%m && t%n) {
printf("impossible\n");
return 0;
}
else {
printf("both ");
}
printf("%lld\n",ans);
return 0;
}