クラスによるトライ木の構築 R(Beta)編（paizaランク B 相当）

これまで実装した配列によるトライ木は、1 つの文字列を記録することができるものでした。
ここからはクラス (構造体) を用いたトライ木の実装を行います。クラスを用いることで複数単語を格納できるトライ木を実現することが出来ます。
最初にトライ木の各頂点を表すための Node クラスを作成してください。

・メンバ変数として、子 (その頂点から辺を 1 つ通って進める頂点) を指すためのメンバ変数 child[] を持ちます。
・child[] はアルファベット小文字 a~z を引数とし、子の情報を返します。具体的にはポインタや参照渡しなどによって別の Node 型のインスタンスを指せるようにすれば良いです。
もし child[a] が初期値の場合、その頂点に 'a' というラベルを持つ出ていく辺とそれによって進める頂点は存在しません。何らかの要素を指す場合、それが 'a' というラベルを持つ辺によって進める頂点です。他の文字 b~z についても同様です。
・Node はそのコンストラクタで child[] の全ての要素がどの頂点も指さないようにする初期化を行います。C++ でポインタを使用して実装する場合には、初期値として nullptr を用いてください。Pythonでは None を用いてください。


もし、リストや二分木などのデータ構造を実装した経験があれば「次に来る要素を指す」という点が似ているかと思います。


ここで、根を始点として有向辺に沿ってある頂点 u に移動したとします。そして、通った経路のラベルを順に読んで得られる文字列を X とします。このとき、u を「X に対応する頂点, または単に頂点 X」と呼びます。

ある文字列 S をトライ木に格納したい場合、次のような手順を踏んでください。
S の i 文字目を S_i, S の長さを |S| とします。
1. 最初に Node 型 の配列 trie を作成してください。trie の要素数は |S|+1 で、それぞれの要素がトライ木の各頂点を表します。
2. trie[i] を S の長さ i のプレフィックスに対応する頂点とします。trie[0] は根です。
3. 0≦i<|S| の範囲で i が 小さいものから順に trie[i] のメンバ変数 child[S_{i+1}] が trie[i+1] を指すようにしてください。



例えば S = "tree" の場合、トライ木は次の図のように構築されていきます。



文字列 S が与えられます。次の手順にしたがって S を格納したトライ木を構築してください。
その後, 以下の Q 個のクエリにこたえてください。
・入力として整数 X が与えられます。S の長さ X のプレフィックスに対応する頂点から出ていく辺のラベルを出力してください。 ただし、そのような辺が存在しない場合には # を出力してください。