Untitled

import java.io.*;
import java.util.*;

public class congaline {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("input.txt"));
    // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(System.out);

    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());

    // LinkedList<String> line = new LinkedList<>();
    DoublyLinkedList<String> line = new DoublyLinkedList<>();
    // ListIterator<String> coupleline = line.listIterator(0);
    HashMap<String, ListIterator<String>> couples = new HashMap<>();

    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      String couple1 = st.nextToken();
      String couple2 = st.nextToken();

      line.insertAtEnd(couple1);
      line.insertAtEnd(couple2);
      // line.add(couple1);
      // line.add(couple2);
      // if (i != 0) {
      // }

      // couples.put(couple2, line.listIterator(i));
      // couples.put(couple1, line.listIterator(i + 1));
    }
    st = new StringTokenizer(br.readLine());
    String commands = st.nextToken();
    ListIterator<String> mic = line.listIterator();

    for (int i = 0; i < q; i++) {
      char command = commands.charAt(i);

      if (command == 'F') {
        mic.previous();
      } else if (command == 'B') {
        mic.next();
      } else if (command == 'R') {
        // mic.
      } else if (command == 'C') {

      } else if (command == 'P') {
        mic.next();
        ListIterator<String> temp = couples.get(mic.previous());

        if (temp.hasNext()) {
          temp.next();
          System.out.println(temp.previous());
        } else {
          temp.previous();
        }
        System.out.println(temp.next());
      }
    }
  }
}

class Node<T> {
  Node<T> prev;
  T data;
  Node<T> next;

  Node(T value) {
    prev = null;
    data = value;
    next = null;
  }
}

class DoublyLinkedList<T> {
  Node<T> head = null;
  Node<T> tail = null;

  void insertAtBeginning(T data) {
    Node<T> temp = new Node<>(data);
    if (head == null) {
      head = temp;
      tail = temp;
    } else {
      temp.next = head;
      head.prev = temp;
      head = temp;
    }
  }

  void insertAtEnd(T data) {
    Node<T> temp = new Node<>(data);
    if (tail == null) {
      head = temp;
      tail = temp;
    } else {
      tail.next = temp;
      temp.prev = tail;
      tail = temp;
    }
  }

  void insertAtPosition(T data, int position) {
    Node<T> temp = new Node<>(data);
    if (position == 1) {
      insertAtBeginning(data);
    } else {
      Node<T> current = head;
      int currPosition = 1;
      while (current != null && currPosition < position) {
        current = current.next;
        currPosition++;
      }
      if (current == null) {
        insertAtEnd(data);
      } else {
        temp.next = current;
        temp.prev = current.prev;
        current.prev.next = temp;
        current.prev = temp;
      }
    }
  }

  void deleteAtBeginning() {
    if (head == null) {
      return;
    }

    if (head == tail) {
      head = null;
      tail = null;
      return;
    }

    Node<T> temp = head;
    head = head.next;
    head.prev = null;
    temp.next = null;
  }

  void deleteAtEnd() {
    if (tail == null) {
      return;
    }

    if (head == tail) {
      head = null;
      tail = null;
      return;
    }

    Node<T> temp = tail;
    tail = tail.prev;
    tail.next = null;
    temp.prev = null;
  }

  void deleteAtSpecificPosition(int pos) {
    if (head == null) {
      return;
    }

    if (pos == 1) {
      deleteAtBeginning();
      return;
    }

    Node<T> current = head;
    int count = 1;

    while (current != null && count != pos) {
      current = current.next;
      count++;
    }

    if (current == null) {
      System.out.println("Position wrong");
      return;
    }

    if (current == tail) {
      deleteAtEnd();
      return;
    }

    current.prev.next = current.next;
    current.next.prev = current.prev;
    current.prev = null;
    current.next = null;
  }

  void display() {
    Node<T> temp = head;
    while (temp != null) {
      System.out.print(temp.data + " --> ");
      temp = temp.next;
    }
    System.out.println("NULL");
  }
}