[POI2008]Poc

有 $n$ 列火车，每列火车有 $l$ 节车厢，每节车厢有一种颜色（用小写字母表示）。接下来会依次进行 $m$ 次车厢交换操作。

对于每列火车，求在交换车厢的某个时刻，与它颜色完全相同的火车最多有多少列。

输入格式

第一行三个整数 $n, l, m$。

接下来 $n$ 行，每行一个长度为 $l$ 的字符串，描述一列火车各节车厢的颜色。

接下来 $m$ 行，每行四个整数 $a, b, c, d$，表示把第 $a$ 列火车的第 $b$ 个字符与第 $c$ 列火车的第 $d$ 个字符交换。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示在交换车厢的某个时刻，与第 $i$ 列火车颜色完全相同的火车的最多数目。

样例输入

5 6 7
ababbd
abbbbd
aaabad
caabbd
cabaad
2 3 5 4
5 3 5 5
3 5 2 2
1 2 4 3
2 2 5 1
1 1 3 3
4 1 5 6

样例输出

3
3
3
2
3

数据范围

• $2\le n\le 1000$；
• $1\le l\le 100$；
• $0\le m\le 10^5$。

来源与许可

本题为 POI 2008 试题「Poc」，题面与测试数据整理自 BZOJ 1125。

样例 1

输入

5 6 7
ababbd
abbbbd
aaabad
caabbd
cabaad
2 3 5 4
5 3 5 5
3 5 2 2
1 2 4 3
2 2 5 1
1 1 3 3
4 1 5 6

输出

3
3
3
2
3