Reconstructing the Hidden Ladder Row

There are k participants in a ladder game. The participants are represented by the first k uppercase English letters, and their initial order is always A, B, C, ....

The figure below shows one ladder with k = 10, ten vertical lines, and five horizontal rows.

In each horizontal row, * means that there is no connecting bar at that position, and - means that a bar connects the two neighboring vertical lines. Following the ladder above gives the final order A, C, G, B, E, D, J, F, I, H from left to right.

A participant moves downward along a vertical line. Whenever the participant meets a horizontal bar, the participant crosses it to the neighboring vertical line and then continues downward. Because of this rule, two horizontal bars cannot occupy adjacent positions in the same row.

Exactly one horizontal row of the ladder is hidden. Reconstruct that row by deciding where to place connecting bars so that the final order after following the whole ladder matches the given order.

Each row of the ladder is given as a string of length k-1. A position without a bar is written as *, and a position with a bar is written as -. The hidden row is written as a string of k-1 question marks.

The first line contains the number of participants k. (3 <= k <= 26)

The second line contains the number of horizontal rows n. (3 <= n <= 1,000)

The third line contains a length-k uppercase string representing the final order after all participants finish the ladder.

The next n lines describe the horizontal rows of the ladder from top to bottom. Each line is either a length-k-1 string consisting of * and -, or a length-k-1 string of question marks representing the hidden row.

Print the reconstructed hidden row that makes the given final order possible. The output must be a length-k-1 string consisting of * and -.

If no valid hidden row can make the given final order, print a length-k-1 string consisting only of x.