トライ木の構築 COBOL(Beta)編（paizaランク B 相当）

このメニューではトライ木というデータ構造を実装します。トライ木は有向木の一種で主に文字列を記録するためのデータ構造です。
トライ木では頂点とラベル付き有向辺に文字を割り当てて文字列を記録します。
また、トライ木の根 (空白となっている頂点) からラベル付き有向辺をたどることで記録された文字列を取り出すことができます。
トライ木の基本的な操作である文字列の挿入・検索・削除は文字列の長さをMとして全てO(M)で行うことが出来ます。

トライ木は次のような特徴を持つデータ構造です。

・根から i 本の辺を通って進んだ頂点にはトライ木に記録された文字列の i 文字目が格納されています。
・根から i 本の辺を通って進んだ頂点は格納された文字列の長さ i のプレフィックスのいずれかに対応します。
・葉 (出ていく辺を持たない頂点) に対応する文字列は必ずトライ木に記録された要素です。
・葉でない頂点であってもトライ木に記録された要素に対応している場合があります。
・ある頂点 u からある頂点 v にラベル x の付いた辺が出ている場合、 x は u が対応する文字列の次の文字になります。そして u の末尾に x を付け足した文字列は v が対応する文字列となります。


例えば、tree, time, paiza, pathの４つの文字列を持つトライ木は次の図のようになります。



まずは配列を用いた簡単なトライ木の実装を行います。
長さが N の小文字のアルファベットからなる文字列 S が 1 つ与えられます。
S から次のような配列 trie を作成してください。
・ trie はキーとして整数と文字の 2 つを取り、格納する値として文字を取ります。
・ キーとなる整数は 0~N 、 キーとなる文字はアルファベットの小文字 a~z を取ります。
・ 格納する値としてアルファベットの小文字 a~z を取ります。
・ S の i 文字目 (1 ≦ i < N) を S_i としたとき, trie[i][S_i] には S_{i+1} が格納されています。
・ trie[0][a] には S_1 が格納されているものとします。この要素がトライ木の根に対応します。
・ 上記の条件以外の要素には何も格納されていないことを示す文字として # を格納します。

その後、次のような Q 個のクエリが与えられます。
・0 以上の整数 X とアルファベットの小文字 Y が与えられるので trie[X][Y] の要素を出力してください。

例えば、与えられる文字列 S が "tree" の場合、配列 trie によって構成されるトライ木は次の図のようになります。