キーの追加 R(Beta)編（paizaランク B 相当）

1 つ前の問題「構造体によるトライ木の構築」では１つの文字列をトライ木に格納しました。
この問題では複数の文字列を格納できるトライ木を作成します。

トライ木の頂点を表す Node クラスにメンバ変数 is_end: bool を追加してください。
さらにトライ木全体を表すクラス Trie を作成し、Node はその内部クラスとしてください。Node と Trie はそれぞれ次のようなメンバ変数、メンバ関数を持つクラスとなります。

Nodeクラス  //トライ木の各頂点を表すクラス
-----------------------------------
メンバ変数
child[ch]: Node (chをキーとして、頂点の情報を返す配列) //文字 ch をラベルとして持つ辺を通って進める頂点を表す
is_end: bool    //この頂点は格納されたキーの最後の頂点であるか(trueならそう)

Trieクラス  //トライ木全体を表すクラス
-----------------------------------
メンバ変数
root: Node  //トライ木の根を表す
-----------------------------------
メンバ関数
insert(word: string): void   //文字列 word をトライ木に格納する

Trie のメンバ関数 insert(word: string): void を実装してもらいます。
この関数は引数とする文字列 word をトライ木に格納する関数です。この関数では word のプレフィックスに対応する頂点が存在しないときに新しく頂点を作成するという動作が求められます。これは C++, Python ではそれぞれ次のように実装することが出来ます。

// 文字 ch で移動できる新しい頂点を作成する実装例
Node *ptr; // ptrは今いる頂点を表す
ptr->child[ch-'a'] = new Node();  

# 文字 ch 移動できる新しい頂点を作成する実装例 ptrは今いる頂点を表す
ptr.child[ord(ch) - ord("a")] = Trie.Node() 

Node クラスに追加したメンバ変数 is_end はトライ木に "aaa" と "aaaaaaa" のような、一方の文字列のプレフィックスがもう一方の文字列であるような 2 つの異なる文字列が格納されていた場合に "aaa" を識別するために必要になります。
is_end が true である頂点はトライ木に格納された文字列の最後の文字に対応することを示します。つまり、根から is_end が true である頂点への経路の文字列がトライ木に格納された文字列となります。


insert() を用いて文字列 T をトライ木に格納する手順を説明します。
説明のため、文字列 T の i 文字目の文字を T{i} と表記します。また、T の長さを |T| とします。さらに T の先頭から i 文字目 (0≦i≦|T|) までで構成されたプレフィックスを T{:i} と表記します。T{:0} は長さ 0 のプレフィックスです。T{:1}> は T{1} です。T{:|T|} は T そのものです。次の手順に従うことで、T をトライ木に格納できます。

1. 最初は根である trie のメンバ変数 root (ここは T{:0} に対応します) で T{:1} に対応する頂点が存在するかを確認する.
　 もし、そのような頂点が存在しなければ新しく作成し,trie のメンバ変数 child[] の適切な位置に辺を追加する.
2. T{:1} に対応する頂点へと移動する.
3. 手順 1, 2 と同じように, 今いる頂点が T{:i} (0≦i<|T|) に対応するなら T{:i+1} に対応する頂点 (なければ新しく作成する) に
　 進む, という処理を T{:|T|} に到達するまで行う.
4. T{:|T|} に対応する頂点のメンバ変数 is_end を true とする.

たとえばトライ木に "aa" と "ab" が格納される場合、トライ木は次のように構築されていきます。

・aa を格納した後(図1)


・ab{:1} を格納した後(図2)
ab{:1} である "a" は対応する頂点がすでに存在しているためトライ木に変化はありません。


・ab{:2} を格納した後(図3)
ab{:2}である "ab" は対応する頂点が存在しないため、新しく頂点を作成する必要があります。



N 個のアルファベット小文字の文字列 S_1, ..., S_N が与えられます。
各 S_i をトライ木に格納した後, 以下の Q 個のクエリに答えてください。
・X 番目の文字列の長さ Y のプレフィックス S_X{:Y} に対応する頂点から出ている辺のラベルを全て出力してください。
・ただし、そのような辺が存在しない場合には # を出力してください・