题目描述

配点： $250$ 点
人物Xは、$N$ 個のハンドルネーム $S_1,\ S_2,\ ...,\ S_N$ が書かれたリストを見た。
しかし、そのリストの一部は見えない。見えない箇所は ? で表される。
人物Xのハンドルネーム $T$ がもしリストに入った場合、人物X含む $N+1$ 人を辞書順で並び替えたときに何番目の可能性があるか、すべて求めなさい。
ただし、名前が同じ人がいた場合、どちらが先に来る可能性もあることに注意せよ。
見えない部分はないので、3個のハンドルネームを辞書順で表すと、e, petr, tourist の順番である。
よって、e は1番目である。

4
e
e
e
e
e

5
??
??
d?
?e
?f
zzz

7
atcoder
topcoder
codeforces
hackerrank
csacademy
codechef
atcoder
square

7
??i?
?o???g????
??m??x?
?h?????i
s????
?og????
u??
square

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $S_2$ : $S_N$ $T$

输出格式

• 何番目がありうるかをすべて求め、数字の昇順で空白区切りで出力すること。(最後の数字の後には空白をつけない)
• また、最後には改行を入れること。

2
tourist
petr
e

1

1 2 3

1 2 3 4 5

6

7

1 2 3 4 5 6 7

提示

制約

• $1\ <\ =\ N\ <\ =\ 10000$
• $1\ <\ =\ |S_i|,\ |T|\ <\ =\ 20$ (ここでは $|A|$ を文字列 $A$ の長さとする)
• $S_i$ は英小文字または ? で構成される。
• $T$ は英小文字で構成される。

得点

小課題1 [ $130$ 点 ]

• リストに見えない部分が存在しない。

小課題2 [ $120$ 点 ]

• 追加の制約はない。

Sample Explanation 2

もし、?o?r?s? が tourist であり、?et? が petr の場合、e, petr, tourist の順になり、e は1番目になる。 もし、?o?r?s? が aobrcsd であり、?et? が petr の場合、aobrcsd, e, petr の順になり、e は2番目になる。 もし、?o?r?s? が aobrcsd であり、?et? が dete の場合、aobrcsd, dete, e の順に並び、e は3番目になる。 よって、すべての可能性がありうる。

Sample Explanation 3

同じ名前の人が複数人いる場合、どの位置に来る可能性もあることに注意せよ。