题目描述

题目译自 XV OI Olimpiada Informatyczna – II etap Pociągi

拜托西亚将举办彩色火车游行。拜托车站的技术轨道上，准备工作如火如荼。车站有 $n$ 条平行轨道，编号 $1$ 至 $n$。第 $i$ 轨道停放编号 $i$ 的火车。每火车包含 $l$ 节车厢，每节涂以 $26$ 种颜色之一（用英文字母小写 a 至 z 表示）。若两火车对应车厢颜色相同，则称其外观相同。

游行每分钟由站内吊车交换一对车厢。正式游行定于明日，今天调度员 Bajtazar 密切观察彩排，记录每对交换车厢的序列。

Bajtazar 不喜过多火车外观雷同。他希望你为每火车 $p$ 计算某一时刻与该火车外观相同的火车最大数量。

编写程序：

• 从标准输入读取轨道上火车描述及车厢交换序列。
• 为每火车计算某一时刻与它外观相同的火车最大数量。
• 将结果输出到标准输出。

输入格式

第一行包含三个自然数 $n, l, m$ $(2 \leq n \leq 1000, 1 \leq l \leq 100, 0 \leq m \leq 100000)$，分别表示火车数、每火车车厢数和交换次数。接下来的 $n$ 行描述各火车，第 $k$ 行包含 $l$ 个英文字母小写，表示第 $k$ 火车车厢颜色。其后 $m$ 行描述交换操作，第 $r$ 行包含四个整数 $p_1, w_1, p_2, w_2$ $(1 \leq p_1, p_2 \leq n, 1 \leq w_1, w_2 \leq l, p_1 \neq p_2$ 或 $w_1 \neq w_2)$，表示第 $r$ 次操作交换火车 $p_1$ 的第 $w_1$ 节车厢与火车 $p_2$ 的第 $w_2$ 节车厢。

输出格式

输出 $n$ 行，第 $k$ 行包含一个整数，表示某一时刻与火车 $k$ 外观相同的火车数量。

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

对于火车 $1, 2, 3$，最大相同数出现在时刻 $4$（彼此相同）。对于火车 $5$，最大相同数出现在时刻 $5$ 和 $6$。对于火车 $4$，最大相同数出现在时刻 $2$。