Punch Card Stacking

We are given n punched cards and a target string s of length m (with LaTeX: \(m=|s|\)). Each card is a string of length m that consists of uppercase letters and holes. A hole is represented by the character * and indicates an empty position.

The task is to arrange all the cards in a certain order (a permutation of the n cards) such that when they are stacked from top to bottom the "visible" letter for each column matches the corresponding character in s. More formally, for each column index \(i\) (\(1 \le i \le m\)), when scanning the stacked cards from top to bottom, the first card whose i-th position is not a hole (*) will determine the visible letter at that column. This letter must equal the \(i\)-th character of s (i.e. \(s_i\)). If for some column \(i\) no card has a letter (i.e. every card has a hole in that column), then it is impossible to obtain s.

Hint (Constraints via Ordering): For each column \(i\), let \(U_i\) be the set of cards that have the letter \(s_i\) in that column, and let \(V_i\) be the set of cards that have a letter different from \(s_i\) (and are not holes) in that column. In any valid stacking order, every card in \(U_i\) must appear above every card in \(V_i\). Using these constraints a topological order can be derived if a solution exists.

inputFormat

The input consists of:

• The first line contains an integer n and the target string s (\(m=|s|\)).
• The following n lines each contain a string of length m, representing a punched card. Each character is either an uppercase letter or * indicating a hole.

outputFormat

If there exists an ordering of the cards such that, after stacking them, the visible letter of column \(i\) equals the \(i\)-th character of s for all \(1 \le i \le m\), then output a permutation of indices (1-indexed) separated by a space. If there are multiple valid orders, any one is accepted. If no such ordering exists, print -1.

sample

3 abc
a*c
ab*
*bc

1 2 3