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

public class QueueSort<E extends Comparable<E>, except> {

    private ArrayQueue<ArrayQueue<E>> Q;
    public static final int CAPACITY = 10; // default queue capacity
    private int n;
    private boolean trace;

    public QueueSort() {
        this(CAPACITY);
    }

    public QueueSort(int capacity) {
        n = capacity;
        Q = new ArrayQueue<ArrayQueue<E>>(n);
    }

    private ArrayQueue<E> merge(ArrayQueue<E> q1, ArrayQueue<E> q2) throws ArrayQueueException {

        ArrayQueue<E> q3 = new ArrayQueue<E>( q1.size()+q2.size() );

        while ( q1.isEmpty() && q2.isEmpty() ) {
            //E q1Element = q1.dequeue();
            //E q2Element = q2.dequeue();

            if ( q1.front().compareTo(q2.front()) > 0) {
                q3.enqueue(q2.dequeue());
            } else {
                q3.enqueue(q1.dequeue());
            }

            if ( q1.front().compareTo(q2.front()) == 0) {
                q3.enqueue(q2.dequeue());
                q3.enqueue(q1.dequeue());
            }

        }

        while ( q1.size()>0 ) {
            q3.enqueue(q1.dequeue());
            q3.enqueue(q2.dequeue());
        }

        return q3;
    }
    //
    // IMPLEMENT ME
    // Take two sorted queues and merge them to produce a third
    // sorted queue
    //

    public void sort() {
        ArrayQueue<E> Q1 = new ArrayQueue<E>(1);
        ArrayQueue<E> Q2 = new ArrayQueue<E>(1);

        while (Q.size() > 1) {
            Q1 = Q.dequeue();
            Q2 = Q.dequeue();
            Q.enqueue( merge(Q1,Q2) );
        }

    }
    //
    // IMPLEMENT ME
    // given a queue Q of queues
    // (1) if Q is of size 1 deliver the first queue in Q
    // (2) if Q is of size 2 or more
    // - get the first and second queues off Q
    // - merge these two queues to create a third queue
    // - add the third queue to the queue
    // - go back to (1)
    //

    public void add(E element) {
        ArrayQueue<E> tempQ = new ArrayQueue<E>(1);
        tempQ.enqueue(element);
        Q.enqueue(tempQ);
    }
    //
    // IMPLEMENT ME
    // create an ArrayQueue<E> that contains the element
    // enqueue it onto Q
    //

    public String toString() {
        return Q.toString();
    }

    public void trace() {
        trace = !trace;
    }

    public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(new File(args[0])); //takes each word
    ArrayList<String> data = new ArrayList<String>();
    while (sc.hasNext()) data.add(sc.next()); //while file not empty, add each word to data (array)
    int n = data.size();
    QueueSort<String> QS = new QueueSort<String>(n);
    for (String s : data) QS.add(s);
    if (args.length > 1) QS.trace();
    QS.sort();
    System.out.println(QS);
    }
}