2194C.md (2544B)
1 Source: https://codeforces.com/problemset/problem/2194/C 2 3 C. Secret message 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Bob, the genius spy, has intercepted an encrypted message. He assumes that it contains secret information and is actively engaged in deciphering it. 22 23 The note, which has fallen into the hands of the spy, consists of $k$ strips, each of length $n$ and containing strict lowercase Latin letters. With extensive experience in deciphering such documents, Bob guessed that the message he is interested in (the deciphering of the note) is also a string of length $n$, and the $i$-th letter of this message corresponds to the $i$-th letter of one of the strips. 24 25 According to Bob, the informativity of a string $s$ is defined as the minimum positive integer $d$ such that a string $t$ of length $d$ exists, and $s$ can be formed by repeating $t$ several times. For example, the informativity of the string "aaaa" is 1, the informativity of the string "abab" is 2, and the informativity of the string "abcd" is 4. 26 27 Bob assumes that the note's author, to ensure reliable transmission of information, repeated the data in the message several times. Therefore, he believes that a more plausible decryption of the note would have the smallest possible informativity. 28 29 Help the spy: find the message that represents the decryption of the note and has the minimum possible informativity. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 In the first line of each test case, there are numbers $n$ and $k$ ($2 \leq n, k \leq 50\,000, 4 \leq n \cdot k \leq 10^5$) — the length of the strips of paper and the number of strips. 36 37 In each of the following $k$ lines of each test case, there is a sequence of $n$ lowercase Latin letters — the next strip. 38 39 It is guaranteed that the sum $n \cdot k$ across all test cases does not exceed $10^5$ 40 41 Output 42 43 For each test case, output a string of length $n$ — the decryption of the note, which has the minimal possible informativity. If there are multiple suitable answers, any of them may be output. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 3 2 53 54 abc 55 56 baa 57 58 9 2 59 60 iiinnnfff 61 62 nnfiffinn 63 64 4 2 65 66 acbd 67 68 bdac 69 ``` 70 71 Output 72 73 ``` 74 aaa 75 76 infinfinf 77 78 acac 79 ``` 80 81 Note 82 83 In the first test case, the minimum possible informativity is $1$: 84 85 abc 86 87 baa 88 89 In the second test case, the minimum possible informativity is $3$: 90 91 iiinnnfff 92 93 nnfiffinn