열차

내일 바이트오티아에서 색깔 열차 퍼레이드가 열린다. 역의 보조 선로에서는 벌써 준비가 한창이다. 역에는 $1$번부터 $n$번까지 번호가 붙은 평행한 선로 $n$개가 있고, $i$번 열차는 $i$번 선로에 서 있다. 모든 열차는 $l$량의 객차로 이루어지며, 각 객차는 영어 소문자로 나타내는 $26$가지 색 가운데 하나로 칠해져 있다. 두 열차는 모든 위치에서 객차 색이 서로 같을 때 똑같아 보인다고 한다.

리허설이 진행되는 동안 크레인이 객차 쌍의 자리를 계속 맞바꾼다. 배차원은 리허설 전체를 지켜보며 교환이 일어난 순서를 모두 적어 두었다. 그는 똑같아 보이는 열차가 많은 것을 싫어해서, 각 열차 $p$에 대해 어느 한 순간에 열차 $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$개의 줄에는 교환이 일어나는 순서대로 하나씩 주어진다. 각 줄에는 네 정수 $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 \ne p_2$ 또는 $w_1 \ne w_2$). 이는 $p_1$번 열차의 $w_1$번째 객차와 $p_2$번 열차의 $w_2$번째 객차를 서로 맞바꾼다는 뜻이다.

정확히 $n$개의 줄을 출력한다. $k$번째 줄에는 정수 하나를 출력하며, 이는 초기 배치와 각 교환 직후의 배치를 모두 고려했을 때 어느 한 순간에 $k$번 열차와 똑같아 보이는 열차의 최대 개수(자기 자신 포함)이다.

아래 그림은 객차가 차례로 교환되는 과정을 보여 준다. $(0)$부터 $(7)$까지의 숫자는 각각 초기 상태와 각 교환 직후의 상태를 나타낸다.

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

$1$번, $2$번, $3$번 열차가 이루는 가장 큰 일치 그룹은 시각 $(4)$에 나타나며, 이때 세 열차가 모두 aaabbd이다. $5$번 열차는 시각 $(5)$와 $(6)$에서 최댓값에 이른다. $4$번 열차는 시각 $(2)$에서 최댓값에 이르며, 이때 $4$번과 $5$번 선로가 모두 caabbd이다.