Passport

A new planet has been found that looks just like Earth. Each planet has countries numbered from $1$ to $N$. These countries are connected by rail and airlines. If there is an air route between country $i$ and country $j$ that satisfies $i

When you enter each country, you will have the first letter of that country written in your passport. The first letter is a capital letter from 'A' to 'Z'. When you arrived on this planet, you entered country $1$. You are planning to travel in such a way that the string of letters written between your entry into country $1$ and your travel to country $N$, arranged in the order in which you entered the country, is the smallest in dictionary order (the order in which words are arranged in an English-Japanese dictionary).

The first letter of the country and the airline route information are given. Write a program that outputs the string written in the passport when you travel by choosing a route so that the string made by arranging the words in the order they entered the country is the smallest in the lexical order.

Input

The input is given in the following form.

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

In the first line, the number of countries $N$ ($2 \leq N \leq 300,000$) and the number of airline routes $M$ ($0 \leq M \leq 300,000$) are given. In the second line, the first letter $c_i$ of country $i$ ($c_i$ is capitalized) is given. The following $M$ lines are the departure country $u_i$ ($1 \leq u_i < N$) and arrival country $v_i$ ($u_i < v_i \leq N$) of the $i$-th airline route.

Output

Outputs a string created by arranging the letters in the passport.    

Sample Input and Output

Sample Input 1

4 1
A B C D
1 3

Sample Output 1

ABCD

Sample Input 2

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

Sample Output 2

ADUZK

 

---