#P10453. 七夕祭

七夕祭

题目描述

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕,于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由 NNMM 列共计 N×MN \times M 个摊点组成。

虽然摊点种类繁多,不过 cl 只对其中的一部分摊点感兴趣,比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq,希望能够通过恰当地布置会场,使得各行中 cl 感兴趣的摊点数一样多,并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani,摊点已经随意布置完毕了,如果想满足 cl 的要求,唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻,当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间,每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下,至少需要交换多少次摊点。

输入格式

第一行包含三个整数 NNMMTTTT 表示 cl 对多少个摊点感兴趣。

接下来 TT 行,每行两个整数 x,yx, y,表示 cl 对处在第 xx 行第 yy 列的摊点感兴趣。

输出格式

首先输出一个字符串。

如果能满足 Vani 的全部两个要求,输出 both

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多,输出 row

如果只能使各列中 cl 感兴趣的摊点数一样多,输出 column

如果均不能满足,输出 impossible

如果输出的字符串不是 impossible, 接下来输出最小交换次数,与字符串之间用一个空格隔开。

2 3 4
1 3
2 1
2 2
2 3
row 1
3 3 3
1 3
2 2
2 3
both 2

提示

对于 30%30\% 的数据,N,M100N,M \le 100

对于 70%70\% 的数据,N,M1000N,M \le 1000

对于 100%100\% 的数据,1N,M1000001 \le N,M \le 1000000Tmin(N×M,100000)0 \le T \le \min(N\times M,100000)1xN1 \le x \le N1yM1 \le y \le M