E. Finch Sanctuaries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Darwin is currently researching various traits of his $$$n$$$ finches that are each currently stored in their own sanctuary. He is trying to understand which finches might be evolutionarily related, so he wants to group them together based on common traits. Specifically, Darwin cares about $$$k$$$ traits of these finches, and has labeled every variant of each trait with a letter between 'a' and 'j'. There is a lot of coordination to be done in moving these finches around so Darwin needs your help processing and keeping track of all the information. Specifically, there are three types of queries he can request of you:

  1. Since he discovered that trait $$$j$$$ is a key indicator of genetic similarity, combine any groups with finches which share a value of this trait.
  2. Compute how many birds are currently in Finch $$$i$$$'s sanctuary (including Finch $$$i$$$ itself)?
  3. Compute how many birds are in the most populated sanctuary?
Input

The first line contains three integers $$$n$$$, $$$k$$$, and $$$q$$$. ($$$1 \leq n, k, q \leq 10^5, nk \leq 10^6$$$) — the number of birds, the number of traits, and the number of queries, respectively.

The next $$$n$$$ lines contain a string $$$s_i$$$ ($$$|s_i| = k$$$) — the values of the $$$k$$$ traits of the bird, respectively. Every trait value is a character between 'a' and 'j'.

The next $$$q$$$ lines contain a description of the corresponding query. The line begins with an integer $$$t$$$ ($$$t \in \{1, 2, 3\}$$$.

  • If $$$t = 1$$$, then the line contains another integer $$$j$$$ ($$$1 \leq j \leq k$$$) — the trait which finches should now also be grouped by.
  • If $$$t = 2$$$, then the line contains another integer $$$i$$$ ($$$1 \leq i \leq n$$$) — the finch which the second query should be performed on.
  • If $$$t = 3$$$, then there is nothing else on the line.

It is guaranteed that there is at least one query of type two or three. Note that queries of type 1 may be repeated.

Output

Output the answers for the second and third queries in order on their own lines.

Example
Input
4 5 14
abcdj
acdei
bcffh
bffgg
2 4
3
1 3
2 3
2 1
3
1 1
2 3
2 1
3
1 2
2 3
2 1
3
Output
1
1
2
1
2
2
2
2
4
4
4