問題文

(難易度目安:$550$点)

$N$行$N$列の、英小文字$[a-z]$のみから構成される行列$M$があります。

ここに $(i,j) := Mのi行j列目の位置$ と定義します。

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

なお定義よりこのような道のりは$Comb(2N-2,N-1)$通りあります。

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

◎このクエリにおいては$(※)$の道のりのうち、$(X,Y)$を通るものだけを考える。

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

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

制約

・$1\le N \le 1000$

・$1\le Q \le 1000$

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

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

・クエリによって与えられる位置$(X,Y)$は$1 \le X,Y \le N$を満たす。

入力

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

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

出力

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

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

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

サンプル

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

icaongd
imlfood
icpchgd

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

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

・$(1,1) → (1,2) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4)$

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

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

・$(1,1) → (2,1) → (3,1) → (4,1) → (4,2) → (4,3) → (4,4)$

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

③$(1,4)$を通る道のりは以下の一つしかありません。

・$(1,1) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4) → (4,4)$

この道順に沿って得られる文字列は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