接頭辞ベースのデータベース (Prefix Based Database)
最初は空のデータベースが与えられ、これに対して一連のクエリを処理する必要があります。クエリには「Add」と「Search」の2種類があり、「Add」クエリでは名前をデータベースに追加し、「Search」クエリでは指定した接頭辞（prefix）で始まるデータベース内の名前を、辞書順で出力するよう要求されます。ただし、その接頭辞に一致する名前が20件を超える場合は、先頭の20件だけを表示してください。
入力
入力の最初の行には整数
q (1 ≤ q ≤ 200 000) が与えられ、これはクエリの数を意味します。続く q 行には、それぞれ以下の形式でクエリが含まれます:- 「Add」クエリ:
add s（ここでsはデータベースに追加する名前）
- 「Search」クエリ:
search p（ここでpは検索する接頭辞）
クエリに使用される文字列の長さは、いずれも20文字を超えません。
出力
「Search」クエリが与えられるたびに、指定した接頭辞で始まるデータベース内の名前を、スペース区切りで出力してください。該当する名前が20件を超える場合は、先頭の20個のみを出力してください。
例
入力 | 出力 |
9
add cat
add code
add core
search co
add profound
add found
search fo
add fight
search f | code
core
found
fight
found |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB