首先我们可以发现，我们只会交换相邻的两个数，所以我们可以把行和列分开来做。

接着考虑对于数组 $a_1, a_2, …, a_n$ 的最小交换次数。

先思考当前 $1$ 和 $n$ 不能互相交换的情况。

由于最后 $a$ 中的每个数都要变为 $a$ 的平均值 $\overline{x}$，所以我们记 $c_i = a_i - \overline{x}$，然后我们用一个前缀和数组 $S$，记录 $c$ 的前缀和。

那么 $\sum_{i = 1}^{n} |S_i|$ 即为答案。

为什么是这样的呢？我们可以举一个例子。

$A: 1\ 3\ 2\ 7\ 7$

$C: -3 -1 -2\ 3\ 3$

$S: -3 -4 -6 -3\ 0$

发现了吗？$S_1$ 记录了 $C_1$ 应该被 $C_2$ 给 $3$，但是 $C_2$ 本身就是 $-1$，又要考虑给 $C_1$ 的问题，所以 $C_2$ 总共需要 $C_3$ 给它 $4$，$C_3$ 同理，需要 $C_4$ 的 $6$。到了 $C_4$，它本身拥有 $3$，所以还需要 $C_5$ 给它 $3$。

这样子我们就可以不重不漏地计算出答案。

回到本题，从上述做法的线性改为了环形。注意到（注意力惊人）一定存在最优解不是环而是链，所以我们可以枚举环的断点，用链的做法去做。

证明如下：
来自 @AcWing 东边的西瓜皮

我们假设断点为 $k$，那么原前缀和序列的顺序就成了 $S_{k+1},…,S_n,S_1,…,S_k$，我们考虑修改过后的前缀和数组，即为 $G$。

$G_{k + 1} = S_{k + 1} - S_k$

$G_{k + 2} = S_{k + 2} - S_k$

$…$

$G_n = S_n - S_k$

$G_1 = S_1 + S_n - S_k$

$G_2 = S_2 + S_n - S_k$

$…$

$G_k = S_k + S_n - S_k$

由于 $S_n$ 为 $0$，所以 $G_i = S_i - S_k$

所以找出使得 $\sum_{i = 1}^{n}|S_i - S_k|$ 最小的 $k$ 即可。这很明显是货仓选址问题，所以 $k = \frac{(n + 1)}{2}$

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m, T;
int row[N], col[N];
int a[N], b[N];
int main() {
    scanf("%d%d%d", &n, &m, &T);
    while (T --) {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x] ++, col[y] ++;
    }
    int averow = 0, avecol = 0;
    for (int i = 1; i <= n; i ++) averow += row[i];
    for (int i = 1; i <= m; i ++) avecol += col[i];
    bool f1 = true, f2 = true;
    if (averow % n != 0) f1 = false;
    if (avecol % m != 0) f2 = false;
    if (!f1 && !f2) {
        printf("impossible");
        return 0;
    } else if (!f1) {
        printf("column ");
    } else if (!f2) {
        printf("row ");
    } else {
        printf("both ");
    }
    long long ans = 0;
    if (f1) {
        averow /= n;
        a[1] = 0;
        for (int i = 2; i <= n; i ++) a[i] = a[i - 1] + row[i] - averow;
        sort(a + 1, a + 1 + n);
        long long res = 0;
        for (int i = 1; i <= n; i ++) 
            res += abs(a[i] - a[n + 1 >> 1]);
        ans += res;
    }
    if (f2) {
        avecol /= m;
        b[1] = 0;
        for (int i = 2; i <= m; i ++) b[i] = b[i - 1] + col[i] - avecol;
        sort(b + 1, b + 1 + m);
        long long res = 0;
        for (int i = 1; i <= m; i ++) 
            res += abs(b[i] - b[m + 1 >> 1]);
        ans += res;
    }
    printf("%lld\n", ans);
    return 0;
}