Trains

The Trains of Colour Parade opens tomorrow in Byteotia, and the crews are already busy on the station's auxiliary tracks. The station has $n$ parallel tracks numbered from $1$ to $n$, and train number $i$ stands on track $i$. Every train is made of $l$ cars, and each car is painted in one of $26$ colours, written as a lowercase letter of the English alphabet. Two trains look the same when their cars match colour for colour in every position.

During the rehearsal a crane keeps swapping pairs of cars. The dispatcher watched the whole rehearsal and wrote down the sequence of swaps. He dislikes seeing many identical trains, so for every train $p$ he wants to know the largest number of trains (train $p$ included) that look the same as $p$ at one and the same moment.

Write a program that:

• reads the initial trains and the sequence of car swaps,
• for each train finds the maximum number of trains that look the same as it at some single moment,
• prints those numbers.

The first line holds three integers $n$, $l$, and $m$ ($2 \le n \le 1{,}000$, $1 \le l \le 100$, $0 \le m \le 100{,}000$): the number of trains, their common length, and the number of car swaps. Each of the next $n$ lines holds a string of $l$ lowercase letters; the $k$-th of these lines gives the colours of the cars of the train on track $k$, from the first car to the last. Each of the following $m$ lines describes one swap, given in the order the swaps happen. A swap line holds four integers $p_1$, $w_1$, $p_2$, $w_2$ ($1 \le p_1, p_2 \le n$, $1 \le w_1, w_2 \le l$, with $p_1 \ne p_2$ or $w_1 \ne w_2$): car $w_1$ of train $p_1$ is exchanged with car $w_2$ of train $p_2$.

Print exactly $n$ lines. The $k$-th line holds one integer: the maximum number of trains (train $k$ included) that look the same as train $k$ at some single moment, taken over the initial arrangement and every arrangement right after a swap.

The diagram below shows the cars being swapped step by step. The numbers $(0)$ through $(7)$ mark the initial state and the state right after each swap.

time      (0)     (1)     (2)     (3)     (4)     (5)     (6)     (7)
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

For trains $1$, $2$, and $3$ the largest matching group appears at time $(4)$, when all three read aaabbd. Train $5$ reaches its maximum at times $(5)$ and $(6)$. Train $4$ reaches its maximum at time $(2)$, when tracks $4$ and $5$ both read caabbd.