Byteotia 的彩色火车游行明天就要开始了。车站的辅助轨道上正在进行紧张的筹备工作。车站有 $n$ 条平行轨道，编号从 $1$ 到 $n$。第 $i$ 号火车占据第 $i$ 条轨道。每列火车由 $l$ 节车厢组成，每节车厢都涂有 26 种颜色之一（用小写英文字母表示）。如果两列火车对应的车厢颜色相同，我们就说这两列火车看起来是一样的。

在游行过程中，起重机会交换某些车厢的位置。然而，真正的游行将在明天举行。今天，调度员 Byteasar 密切观察了彩排，并记录下了车厢交换的序列。

Byteasar 特别不喜欢有很多火车看起来一样。对于每一列火车 $p$，他想计算在某个时刻，看起来与当时火车 $p$ 一样的火车的最大数量。

请编写一个程序：

• 读取火车占据轨道的情况以及车厢交换序列的描述，
• 对于每一列火车，确定在某个时刻看起来与它一样的火车的最大数量，
• 输出结果。

输入格式

输入的第一行包含三个整数 $n$、$l$ 和 $m$（$2 \le n \le 1\,000$，$1 \le l \le 100$，$0 \le m \le 100\,000$），分别表示火车的数量、火车的公共长度以及车厢交换的次数。接下来的 $n$ 行包含各轨道上火车的描述。第 $k$ 行包含 $l$ 个小写英文字母，表示第 $k$ 列火车各车厢的颜色。随后是 $m$ 行描述车厢交换的记录，按交换发生的顺序排列。第 $r$ 行包含四个整数 $p_1$、$w_1$、$p_2$、$w_2$（$1 \le p_1, p_2 \le n$，$1 \le w_1, w_2 \le l$，$p_1 \neq p_2$ 或 $w_1 \neq w_2$），表示第 $r$ 次车厢交换，即将第 $p_1$ 号火车的第 $w_1$ 节车厢与第 $p_2$ 号火车的第 $w_2$ 节车厢进行交换。

输出格式

程序应输出恰好 $n$ 行。第 $k$ 行应包含一个整数，表示在某个时刻看起来与第 $k$ 号火车一样的火车的最大数量。

样例

输入 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

输出 1

3
3
3
2
3

说明

下图展示了连续的车厢交换过程：

track 1:  ababbd    ababbd    ababbd    ababbd    aaabbd    aaabbd    aaabbd    aaabbd
track 2:  abbbbd    ababbd    ababbd    aaabbd    aaabbd    acabbd    acabbd    acabbd
track 3:  aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd
track 4:  caabbd    caabbd    caabbd    caabbd    cabbbd    cabbbd    cabbbd    dabbbd
track 5:  cabaad    cabbad    caabbd    caabbd    caabbd    aaabbd    aaabbd    aaabbc
           (0)       (1)       (2)       (3)       (4)       (5)       (6)       (7)

在时刻 (4)，看起来与第 1、2 或 3 号火车中任意一列一样的火车数量达到最大（此时这三列火车看起来都一样）。对于第 5 号火车，其最大值出现在时刻 (5) 和 (6)。对于第 4 号火车，其最大值出现在时刻 (2)。