Secret message

For each column $i$, the final message may use any lowercase letter that appears at position $i$ in at least one strip. So compress the input into masks:

$$mask[i] = \{\text{letters available at column } i\}.$$

Now forget the strips. The problem is: choose one character from each $mask[i]$ so that the resulting string has the smallest possible informativity.

If a string of length $n$ has informativity $d$, then it is exactly some block of length $d$ repeated $n/d$ times. So $d$ must divide $n$. No need to test random lengths; that would be chasing ghosts.

For a fixed divisor $d$, all positions with the same remainder modulo $d$ must be equal:

$$r,\ r+d,\ r+2d,\dots$$

Suppose their common character is $c$. Then $c$ must be allowed in every column in that residue class. Therefore, for each residue $r$, we need:

$$mask[r] \ \&\ mask[r+d] \ \&\ mask[r+2d] \ \&\ \cdots \ne 0.$$

If this intersection is nonzero for every $r \in [0,d-1]$, then period $d$ is possible. Pick any character from each intersection and repeat those $d$ characters to build the answer.

So the algorithm is simple:

1. Build the column masks from the $k$ strips.
2. List all divisors of $n$ and sort them increasingly.
3. For each divisor $d$:
   • compute the intersection mask for each residue class modulo $d$;
   • if every intersection is nonzero, construct the answer and stop.

Why this is correct:

If the algorithm accepts some $d$, then for every residue class modulo $d$ it found a character available in every column of that class. Filling all those positions with that character creates a valid message with period $d$, so its informativity is at most $d$.

If a valid message has informativity $d$, then every residue class modulo $d$ is filled by one repeated character. Since the message is valid, that character must be available in every column of the class. Thus the bitwise intersection for every class must be nonzero. So the algorithm will accept every feasible period $d$.

Because we test divisors in increasing order, the first accepted $d$ is the minimum possible informativity. Done.

Edge cases are pretty tame:

• If $d=1$, all columns must share one common letter.
• If nothing smaller works, $d=n$ always works, because each residue class contains exactly one column and every column has at least one available letter.
• Duplicate letters in a column do not matter; masks naturally ignore them.

Let $S = n \cdot k$ for one test case. Building masks costs $O(S)$. Checking one divisor costs $O(n)$, and $n \le 50000$, so the number of divisors is small enough for this directly. The total complexity is

$$O(nk + n\tau(n)),$$

where $\tau(n)$ is the number of divisors of $n$. Memory usage is $O(n).