パスポート

地球にそっくりな新たな惑星が見つかりました。その惑星にはそれぞれ$1$から$N$までの番号がついた国があります。これらの国は鉄道路線と航空路線でつながっています。鉄道路線を使うと、どの国$i$からでも、その隣の国$i+1$へ入国できます。$i < j$を満たす国$i$と国$j$の間に航空路線が開設されていると、国$i$から国$j$へ直接入国できます。

各国に入国すると、あなたのパスポートにその国の頭文字を書いてもらえます。頭文字はAからZまでの英大文字です。この惑星にやってきたあなたは、国$１$に入国しました。国$１$に入国してから国$N$まで移動する間に書かれた文字を、入国した順番に並べて作った文字列が、辞書式順序（英和辞書で単語が並んでいる順番）で最小になるという条件で旅行を計画しています。

国の頭文字と航空路線の情報が与えられる。入国した順に並べて作った文字列が辞書式順序で最小になるように経路を選んで旅行したとき、パスポートに書かれている文字列を出力するプログラムを作成せよ。

入力

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

$N$ $M$
$c_1$ $c_2$ ... $c_N$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_M$ $v_M$

１行目に国の数$N$ ($2 \leq N \leq 300,000$)と航空路線の数$M$ ($0 \leq M \leq 300,000$)が与えられる。2行目に国$i$の頭文字$c_i$ ($c_i$は英大文字)が与えられる。続く$M$行に$i$番目の航空路線の出発国$u_i$ ($1 \leq u_i < N$)と到着国$v_i$ ($u_i < v_i \leq N$)が与えられる。

出力

パスポートに書かれている文字を並べて作った文字列を出力する。  

入出力例

入力例１

4 1
A B C D
1 3

出力例１

ABCD

入力例２

6 2
A M D U Z K
1 3
3 5

出力例２

ADUZK

 

---