import java.rmi.server.RMISocketFactory;
import java.util.Scanner;

class DLNode {

  String content;
  DLNode successor; // der, der nach mir gekommen ist
  DLNode predecessor; // der, der zuvor schon da war

  public DLNode(String x) {
    content = x;
    successor = this;
    predecessor = this;
  }
}

public class QueueDLL {

  DLNode first;
  DLNode last;

  public QueueDLL() {
    first = new DLNode(null);
    last  = new DLNode(null);
    first.successor = last; 
    last.predecessor = first; 
  }

  public boolean push(String y) {
    
    DLNode roterKnoten = new DLNode(y);
    DLNode penultimate = last.predecessor;
    penultimate.successor = roterKnoten;
    roterKnoten.predecessor = penultimate;    
    roterKnoten.successor = last;
    last.predecessor = roterKnoten;

    return true;
  }

  public String pop() {   
    DLNode second = first.successor;
    DLNode third = second.successor;

    first.successor = second.successor; 
    third.predecessor = first; 

    return second.content;
  }

  public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    QueueDLL queue = new QueueDLL();
    while (scanner.hasNext()) {
      String s = scanner.next();
      if (s.toLowerCase().equals("pop")) {
        System.out.println(queue.pop());
      } else if (s.toLowerCase().equals("push")) {
        String element = scanner.next();
        if (queue.push(element) == false) {
          System.err.println("Stack capacity reached");
        }
      } else {
        System.err.println("unknown command: " + s);
      }
    }
  }
}
