Problem A
The Amulet
Caitlyn is on another case. Her biggest clue this time is a small amulet containing an $R \times C$ grid of characters. From an informant, she learned that the amulet has a secret code. She’s not sure what the code is yet, but knows it satisfies the following properties:
-
The code appears as a substring in exactly $x$ rows, and does not appear in any other rows.
-
The code appears as a substring in exactly $y$ columns, and does not appear in any other columns.
-
The code is maximal length of all strings that satisfy the first two conditions.
-
The code is lexicographically smallest of all strings that satisfy the first three conditions.
A string appears as a substring in a row if it appears as a contiguous sequence of characters in that row when read from left to right. A string appears as a substring in a column if it appears as a contiguous sequence of characters in that column when read from top to bottom. For two strings of equal length, $S$ and $T$, $S$ is lexicographically smaller than $T$ if there exists an index $k$ such that for all $i < k$, $S_i = T_i$, and $S_k$ precedes $T_k$ in alphabetical order.
Caitlyn knows $x$ and $y$, but she still can’t spot the code, and she’s starting to suspect that the informant was just wasting her time. Can you create an algorithm to help Caitlyn crack the code?
Input
The first line contains four integers $R$, $C$, $x$, and $y$ ($1 \leq R \times C \leq 2 \cdot 10^5$, $0 \leq x \leq R$, $0 \leq y \leq C$, $x + y > 0$). The next $R$ lines each contain a string of length $C$ consisting of lowercase letters a-z, representing the amulet.
Output
Output a single line containing the secret code as described above. If no such code exists, output -1 instead.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 2 2 xba bab acc |
ba |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 2 2 aba bab acc |
ab |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 3 2 2 aba bab abc |
ba |
