Min String Query

(難易度目安:点)

行列の、英小文字のみから構成される行列があります。

ここに と定義します。

いま、からまで、隣接するマスを移りわたることで最短距離で行くような道のりを考えましょう。

なお定義よりこのような道のりは通りあります。

文字列が好きなAliceさんは、以下のクエリに個答えました。

◎このクエリにおいてはの道のりのうち、を通るものだけを考える。

この条件のもとで、道のり上に存在するアルファベットを順番に結合して得られる長さの文字列のうち、考えうる辞書順最小の文字列を求めよ。

Aliceさん同様各クエリに解答してください。

・

・

・は英小文字のみから構成される文字行列である

◉全クエリにおいて以下が成り立つ。

・クエリによって与えられる位置はを満たす。

入力は以下の形式で与えられます。

N
M_11 M_12 ... M_1N
M_21 M_22 ... M_2N
.
.
M_N1 M_N2 ... M_NN
Q
X_1 Y_1
X_2 Y_2
.
.
X_Q Y_Q

全部で行出力してください。

行目には番目のクエリに対する文字列を出力してください。

最後に改行してください。

4
icpc
math
long
food
3
1 1
3 1
1 4

icaongd
imlfood
icpchgd

①を通る道のりはのうち全てです。の道のり全てにおいて、得られる文字列のうち辞書順最小の文字列はicaongdです。

これは、以下のような道のりを通るときに得られます。

・

②を通る道のりはのうち限られます。そのような道のり全てにおいて、得られる文字列のうち辞書順最小の文字列はimlfoodです。

これは、以下のような道のりを通るときに得られます。

・

一つ目のクエリに対して道のりの制約が厳しくなっている以上、得られる文字列は一つ目のクエリの文字列と比較して辞書順で大きくなっています。

③を通る道のりは以下の一つしかありません。

・

この道順に沿って得られる文字列はicpchgdです。

10
itissurpri
singthatit
salmostthe
endoftheye
aritissurp
risingthat
itsalmostt
heendofthe
yearitissu
rprisingth
10
3 1
1 4
1 5
9 2
6 5
2 5
8 9
7 9
1 10
10 1

issaldisialdisingth
itisgmofingmofingth
itissthatheuhatheuh
isianriteearisingth
isialdisingmofingth
isingthatheuhatheuh
isialdisialdoftheuh
isialdisialmostheuh
itissurpriteeptteuh
issearihyrprisingth