Description

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是TYVJ今年举办了一次线下七夕祭。
Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。
矩形的祭典会场由N排M列共计N×M个摊点组成。
虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。
由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在Vani想知道他的两个要求最多能满足多少个。
在此前提下，至少需要交换多少次摊点。

Input

第一行包含三个整数N和M和T，T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。

Output

首先输出一个字符串。
如果能满足Vani的全部两个要求，输出both；
如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；
如果只能使各列中cl感兴趣的摊点数一样多，输出column；
如果均不能满足，输出impossible。
如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

Sample Input

2 3 4
1 3
2 1
2 2
2 3 

Sample Output

row 1 

Hint

$1≤N,M≤100000$
$0≤T≤min(N\cdot M,100000)$
$1≤x≤N,1≤y≤M$

Analyse

• 行与行交换不会影响这一列的总数，列与列交换不会影响这一行的总数，所以我们可以把问题拆成“使每一行相同”+“使每一列相同”

• 拿每一行来讲，显而易见若感兴趣的摊点总数 T 不能被 N 整除，则不可能达到要求，若能，则每一行最后都有 T/M 个感兴趣的摊点。

设每一行原有 C[i] 个感兴趣的摊点，A[i]=C[i]-T/M ，那么最后任意 A[i]=0 ；设 S 数组为 A 数组的前缀和，显而易见 S[N]=0。

假如我们从 1~N 顺序交换，即：
1. 若 C[1]>T/N ，则第一行需要给第二行 A[1] 个摊点，即把 C[2] 加上 A[1]
2. 若 C[1]<T/N ，则第二行需要给第一行 -A[1] 个摊点，即把 C[2] 加上 A[1]（此时 A[1] 为负）

• 以此类推 2~N ，那么所需的最少步数就是 $\sum\limits_{i=1}^{N}|s[i]|$ （注意思考为什么不是 A 求和）

但是呢，我们不一定从 1 开始，该问题为“环形问题”，我们可以任意选择一个起点，不过枚举太慢了。

找规律：
从第一行开始，每一行对应的 A、S 为：
1. A[1]、A[2]…A[N]
2. S[1]、S[2]…S[N]

从第 k+1 行开始，每一行对应的 A、S 为：
1. A[k+1]、A[k+2]…A[N]、A[1]…A[k]
2. S[k+1]-S[k]、S[k+2]-S[k] … S[N]-S[k]、S[1]+S[N]-S[k] … S[k]+S[N]-S[k]

因为 S[N]=0 ，根据上文推的最少步数，$ans=\sum\limits_{i=1}^{N}|S[i]-S[k]|$ ，那么 k 没有必要枚举！这坨玩意看着是不是和“货仓选址”老像了！！只需要把 S 排个序，取中位数 S[k] 就是最优解！！！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int myabs(int a) {return a<0?-a:a;}
ll sum,x[100010],y[100010]/*统计总共、每一行、每一列的感兴趣摊数*/;
ll s[100010];
int main()
{
    int n,m,t;scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=t;i++)
    {
        sum++;
        int X,Y;scanf("%d%d",&X,&Y);
        x[X]++;y[Y]++;
    }
    ll ans1=-1,ans2=-1;
    if(sum%n==0)
    {
        ll ave=sum/n;
        for(int i=1;i<=n;i++) s[i]=x[i]-ave,s[i]+=s[i-1];
        sort(s+1,s+n+1);ans1=0;
        for(int i=1;i<=n;i++) ans1+=myabs(s[i]-s[(n+1)>>1]);
    }
    if(sum%m==0)
    {
        ll ave=sum/m;
        for(int i=1;i<=m;i++) s[i]=y[i]-ave,s[i]+=s[i-1];
        sort(s+1,s+m+1);ans2=0;
        for(int i=1;i<=m;i++) ans2+=myabs(s[i]-s[(m+1)>>1]);
    }
    if(ans1==-1 && ans2==-1) puts("impossible");
    else if(ans1==-1) printf("column %lld\n",ans2);
    else if(ans2==-1) printf("row %lld\n",ans1);
    else printf("both %lld\n",ans1+ans2);
    return 0;
}