Particles in a magnetic field

A physicist in Niels Bohr Institute in Copenhagen is conducting an experiment which aim is to obtain a single particle in a given magnetic field. At the beginning of an experiment, there are more particles of diferent types in the field. All particles are moving along circular trajectories around common center. All trajectories lie in one common plane, creating a system of concentric rings. Each trajectory is occupied by exactly one particle, the distances between the neighbouring trajectories are all equal to one another.
A short laser pulse can change the arrangement of the particles in the field. Specifically, one pulse causes two particles on the immediately neighbouring trajectories to interact. The two interacting particles merge into one resulting particle and some ammount of energy is radiated out. The resulting particle occupies also a circular trajectory, the radii of the other trajectories adjust themselves so that all the distances between the neighbouring trajectories are all equal again. The type of the resulting particle depends on the types of the two merged particles, their order of distance from the common center and the laser pulse characteristics. It does not depend on the momentary position of the particles on their respective trajectories.
The laser pulses can be applied in any order to any two neigbouring trajectories. We say that a particle is produced by the experiment if it is a single particle which remains in the magnetic field after some number of interactions. Each interaction in the experiment may be applied more than once.

     

Image 1. Four particles a, b, a, b (listed from center) in the magentic field. The available interaction types are a b → b, a b → c, b a → a, c c → b. The first row of the scheme illustrates the sequence of interactions in an experiment producing a particle of type b. The second row of the scheme illustrates the sequence of interactions in an experiment producing a particle of type c, It is impossible to produce a particle of type a.

The task

You are given the types and the order of particles in the magnetic field. Also, you are given the list of all possible interactions. Find all types of particles which can be produced in the experiment.

---

Input

The first line contains two positive integers N and P separated by space. N represents the original number of particles in the magnetic field. P represents the number of available interactions. The second line specifies the original positions and types of particles in the experiment. The line contains N characters separated by spaces. Each character represents one particle, the character value is in interval 'a' - 'z' and it represents the particle type. The order of the character corresponds to the order of the particles starting from the common center of their trajectories. Next, there are P lines each of which represents one available interaction. One interaction is specified by three characters I, O, R separated by spaces. The character I specifies the type of interacting particle which is closer to the common center, O specifies the type of interacting particle which is farther from the common center, R specifies the type of the resulting particle. The interaction is applicable only to the particles which occupy immediately neighbouring trajectories.
It holds that 2 ≤ N ≤ 200, 1 ≤ P ≤ 300.

Output

The output contains one line with the list of all particle types which can be produced in the experiment. The list contains characters representing the particle types, the characters are separated by spaces and are sorted in ascending alphabetical order. It is guaranteed that the list is always nonempty for all data sets in this problem.

Example 1

Input

4 4
a b a b
a b b
a b c
b a a
c c b

Output

b c

The data and the solution of the example 1 are depicted in the image 1.

Example 2

Input

9 5
c c e e f e e c c
e f f
c f f
f e f
f c c
c c f

Output

c f

Example 3

Input

22 13
a b a c d f a e b a a g h h g h i j h i j h
a g k 
a k l
b k l
c k l
d k l
e k l
f k l
l g k
l h k
l i k
l j k
l h a
l h j

Output

a j k l

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set