You are given a string ~S~ of length ~N~ and ~Q~ queries. For each query you must print the shortest string that starts with a character ~x_i~ and ends with a character ~y_i~ that only has adjacent characters that are found in ~S~.

For example, if ~S~ is "ajba", then pairs of adjacent letters in your resulting string can only be "aj", "jb", or "ba". Note that "ja" would not be allowed.

If there are multiple answers, print the lexicographically least.

If there is no such string, print -~1~.

Input Specification

The first line will contain two integers ~N~ ~(2 \leq N \leq 10^5)~ and ~Q~ ~(1 \leq Q \leq 10^5)~

The second line will contain the string ~S~ of length ~N~ containing only lowercase English letters.

Lines ~3~ to ~Q+2~ will contain two lowercase English letters ~x_i~ and ~y_i~, ~x_i \neq y_i~

Output Specification

One line per query, the shortest string or -~1~ if none exist.

Sample Input 1

6 2
mcpttq
m t
p q

Sample Output 1

mcpt
ptq