A - Atcoder Handles 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

Max Score: 250 Points

Problem Statement

Mr.X, who the handle name is T, looked at the list which written N handle names, S_1, S_2, ..., S_N.
But he couldn't see some parts of the list. Invisible part is denoted ?.

Please calculate all possible index of the handle name of Mr.X when you sort N+1 handle names (S_1, S_2, ..., S_N and T) in lexicographical order.
Note: If there are pair of people with same handle name, either one may come first.

Input

The input is given from standard input in the following format.
N
S_1
S_2
 :
S_N
T

Output

  • Calculate the possible index and print in sorted order. The output should be separated with a space. Don't print a space after last number.
  • Put a line break in the end.

Constraints

  • 1 ≤ N ≤ 10000
  • 1 ≤ |S_i|, |T| ≤ 20 (|A| is the length of A.)
  • S_i consists from lower-case alphabet and ?.
  • T consists from lower-case alphabet.

Scoring

Subtask 1 [ 130 points ]

  • There are no ?'s.

Subtask 2 [ 120 points ]

  • There are no additional constraints.

Sample Input 1

2
tourist
petr
e

Sample Output 1

1
There are no invisible part, so there are only one possibility. The sorted handle names are e, petr, tourist, so e comes first.

Sample Input 2

2
?o?r?s?
?et?
e

Sample Output 2

1 2 3
If ?o?r?s? is tourist, and ?et? is petr, the sorted handle names are e, petr, tourist, so e comes first.
If ?o?r?s? is aobrcsd, and ?et? is petr, the sorted handle names are aobrcsd, e, petr, so e comes second.
If ?o?r?s? is aobrcsd, and ?et? is dete, the sorted handle names are aobrcsd, dete, e, so e comes third.
So all indexes are possible.

Sample Input 3

4
e
e
e
e
e

Sample Output 3

1 2 3 4 5
If people have same handle name, which one may come first.

Sample Input 4

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

Sample Output 4

6

Sample Input 5

7
atcoder
topcoder
codeforces
hackerrank
csacademy
codechef
atcoder
square

Sample Output 5

7

Sample Input 6

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

Sample Output 6

1 2 3 4 5 6 7

配点： 250 点

問題文

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

入力

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

N
S_1
S_2
 :
S_N
T

出力

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

制約

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

得点

小課題1 [ 130 点 ]

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

小課題2 [ 120 点 ]

  • 追加の制約はない。

入力例1

2
tourist
petr
e

出力例1

1
見えない部分はないので、3個のハンドルネームを辞書順で表すと、e, petr, tourist の順番である。
よって、e は1番目である。

入力例2

2
?o?r?s?
?et?
e

出力例2

1 2 3
もし、?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番目になる。
よって、すべての可能性がありうる。

入力例3

4
e
e
e
e
e

出力例3

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

入力例4

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

出力例4

6

入力例5

7
atcoder
topcoder
codeforces
hackerrank
csacademy
codechef
atcoder
square

出力例5

7

入力例6

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

出力例6

1 2 3 4 5 6 7