**Zadání**\\
Viz odkaz:  [[https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=particles|Částice v magnetickém poli]].\\


=== Nejrychlejší řešení v Javě ===

<code C>
import java.util.*;
import java.io.*;

public class Main {
    HashMap<Pair, ArrayList<Character>> pairs = new HashMap<>();
    Set<String> prosle = new HashSet<>();
    char[] elektrony;
    char[][][] tabulka;
    
    void vyplnTabulku(int level) {
        for (int i = 0; i < elektrony.length; i++) {
            if (level + i == elektrony.length) break;
            char prvni, posledni;
            for (int j = i; j < level + i; j++) {
                int k = 0;
                while (tabulka[i][j][k] != 0) {
                    prvni = tabulka[i][j][k];
                    int q = 0;
                    while (tabulka[j + 1][i + level][q] != 0) {
                        posledni = tabulka[j + 1][i + level][q];
                        Pair p = new Pair(prvni, posledni);
                        aktualizuj(p, i, level + i);
                        q++;
                    }
                    k++;
                }
            }
        }
    }
    
    void aktualizuj(Pair p, int row, int col) {
        if (!pairs.containsKey(p)) return;
        ArrayList<Character> bla = pairs.get(p);
        for (Character character : bla) {
            int k = 0;
            while( tabulka[row][col][k] != 0 & tabulka[row][col][k] != character) {
                k++;
            }
            if (tabulka[row][col][k] == 0) {
                tabulka[row][col][k] = character;
                tabulka[row][col][k + 1] = 0;
            }
        }
    }
    
    void pocitej() {
        for (int i = 1; i < elektrony.length; i++) {
            vyplnTabulku(i);
        }
    }
    
    void printResult() {
        char[] result = tabulka[0][elektrony.length - 1];
        ArrayList<Character> resul = new ArrayList<>();
        for (int i = 0; i < result.length; i++) {
            if (result[i] == 0) break;
            resul.add(result[i]);
        }
        Collections.sort(resul);
        Character[] p = new Character[resul.size()];
        resul.toArray(p);
        for (int i = 0; i < p.length; i++) {
            System.out.print(p[i]);
            if (i != p.length -1) System.out.print(" ");
        }
    }
    
    public void load(int elektronu, int pravidel, BufferedReader br) throws IOException {
        elektrony = new char[elektronu];
        tabulka = new char[elektronu][elektronu][27];
        String line = br.readLine();
        for (int i = 0; i < elektrony.length * 2; i+=2) {
            char c = line.charAt(i);
            elektrony[i/2] = c;
            tabulka[i/2][i/2][0] = c;
        }
        for (int i = 0; i < pravidel; i++) {
            line = br.readLine();
            char prvni = line.charAt(0);
            char druhy = line.charAt(2);
            char vysl = line.charAt(4);
            Pair p = new Pair(prvni, druhy);
            if (!pairs.containsKey(p)) {
                ArrayList<Character> bla = new ArrayList<Character>();
                bla.add(vysl);
                pairs.put(p, bla);
            } else {
                ArrayList<Character> bla = pairs.get(p);
                bla.add(vysl);
            }
        }
        
        
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String cisla = br.readLine();
        StringTokenizer st = new StringTokenizer(cisla, " ");
        String c = st.nextToken();
        int elektronu = Integer.parseInt(c);
        c = st.nextToken();
        int pravidel = Integer.parseInt(c);
        Main main = new Main();
        main.load(elektronu, pravidel, br);
        main.pocitej();
        main.printResult();
    }
    
    private class Pair {
        char prvni;
        char druhy;

        public Pair(char prvni, char druhy) {
            this.prvni = prvni;
            this.druhy = druhy;
        }

        public char getPrvni() {
            return prvni;
        }

        public char getDruhy() {
            return druhy;
        }

        @Override
        public int hashCode() {
            int hash = 3;
            hash = 59 * hash + this.prvni;
            hash = 59 * hash + this.druhy;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Pair other = (Pair) obj;
            if (this.prvni != other.prvni) {
                return false;
            }
            if (this.druhy != other.druhy) {
                return false;
            }
            return true;
        }
    }
}
</code>


=== Nejrychlejší (a jediné) řešení v C/C++ ===

<code C>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <string>

using namespace std;

#define LOG(x) cout << x << endl;
//#define TEST "03"

#define ALPHABET 26
#define CTON(c) ((int)(c - 'a'))
#define NTOC(n) ((char)(n + 'a'))

struct rule {
    int first, second, result;
};

ifstream fin;

int n, p;
bool ***matrix; // matrix of order n * n * ALPHABET, matrix[i][j] contains bit set of particles, which can be released by applying laser to orbits i-j
bool ***rules; // matrix of order ALPHABET * ALPHABET * ALPHABET, rules[i][j] contains all particles produced by colliding particles i and j

void read_input() {
#ifdef TEST
    string path = "/Users/petr/Desktop/datapub/pub";
    path += TEST; path += ".in";
    fin.open(path);
    #define cin fin
#endif
    
    // parse data from cin
    cin >> n >> p;
    
    // alloc matrix and read input sequence of n chars
    matrix = new bool **[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new bool *[n];
        char c; cin >> c; // read one from n particles
        int particle = CTON(c);
        for (int j = 0; j < n; j++) {
            matrix[i][j] = new bool [ALPHABET];
            for (int k = 0; k < ALPHABET; k++) {
                if (i == j && k == particle) {
                    matrix[i][j][k] = true; // initialize matrix on the diagonal
                } else {
                    matrix[i][j][k] = false; // below and above diagonal are 0's
                }
            }
        }
    }
    
    // alloc rules
    rules = new bool **[ALPHABET];
    for (int i = 0; i < ALPHABET; i++) {
        rules[i] = new bool *[ALPHABET];
        for (int j = 0; j < ALPHABET; j++) {
            rules[i][j] = new bool [ALPHABET];
            for (int k = 0; k < ALPHABET; k++) {
                rules[i][j][k] = false;
            }
        }
    }
    
    // read rules
    for (int i = 0; i < p; i++) {
        char ci, co, cv;
        cin >> ci >> co >> cv;
        
        // each row consists of 3 chars: [i] [o] -> [v]
        int ii = CTON(ci);
        int io = CTON(co);
        int iv = CTON(cv);
        
        // flip the proper bit
        rules[ii][io][iv] = true;
    }
}

void compute() {
    // gradually approach top right corner of the matrix
    for (int phase = 1; phase <= n - 1; phase++) {
        // iterate above main diagonal
        for (int field = 0; field < n - phase; field++) {
            // fill field matrix[field][field + phase]
            // use fields matrix[field][field + phase - k] and matrix[field + phase - k + 1][field + phase]
            // where k is from 1..phase
            
            for (int k = 1; k <= phase; k++) {
                for (int particleA = 0; particleA < ALPHABET; particleA++) {
                    if (!matrix[field][field + phase - k][particleA]) {
                        // only proceed, if the particle can be produced
                        continue;
                    }
                    
                    for (int particleB = 0; particleB < ALPHABET; particleB++) {
                        if (!matrix[field + phase - k + 1][field + phase][particleB]) {
                            // only proceed, if the particle can be produced
                            continue;
                        }
                        
                        // use the rules to figure out the output of reaction A + B
                        for (int r = 0; r < ALPHABET; r++) {
                            if (rules[particleA][particleB][r]) {
                                // matching rule found, flip the bit
                                matrix[field][field + phase][r] = true;
                            }
                        }
                    }
                }
            }
        }
    }
}

void cleanup() {
    // do some cleaning up
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            delete [] matrix[i][j];
        }
        delete [] matrix[i];
    }
    delete [] matrix;
    
#ifdef TEST
    fin.close();
#endif
}

void output() {
    bool first = true;
    for (int i = 0; i < ALPHABET; i++) {
        if (matrix[0][n - 1][i]) {
            if (!first) {
                cout << " ";
            }
            
            cout << NTOC(i);
            first = false;
        }
    }
    cout << endl;
}

int main(int argc, const char * argv[])
{
    read_input();
    compute();
    output();
    cleanup();
    
    return 0;
}

</code>