package amphis;

// problème : lire des lignes sur l'entrée standard
// et les imprimer dans l'ordre inverse sur la sortie standard

// ce fichier regroupe de nombreuses solutions,
// dont certaines ont été présentées en amphi et sont
// décrites dans les transparents

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Stack;
import java.util.Vector;

// une solution simple et efficace, utilisant la classe Vector

class Amphi1vector {
  
  public static void main(String[] args) throws IOException {
    Vector<String> v = new Vector<String>();
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    double start = System.currentTimeMillis();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      v.add(s);
    }
    for (int i = v.size() - 1; i >= 0; i--)
      System.out.println(v.get(i));
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }
  
}

// une solution naive, où la taille du tableau est augmentée de 10
// chaque fois que le tableau est plein

class Amphi1myvectornaive {
  
  public static void main(String[] args) throws IOException {
    String[] v = new String[10];
    int size = 0;
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    double start = System.currentTimeMillis();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      if (size == v.length) {
        String[] old = v;
        v = new String[size + 10];
        System.arraycopy(old, 0, v, 0, size);
      }
      v[size++] = s;
    }
    for (int i = size - 1; i >= 0; i--)
      System.out.println(v[i]);
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }
  
}

// une meilleure solution, en doublant la taille au lieu de lui ajouter 10
// (c'est faire la même chose que Vector)

class Amphi1myvector {
  
  public static void main(String[] args) throws IOException {
    String[] v = new String[10];
    int size = 0;
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    double start = System.currentTimeMillis();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      if (size == v.length) {
        String[] old = v;
        v = new String[2 * size];
        System.arraycopy(old, 0, v, 0, size);
      }
      v[size++] = s;
    }
    for (int i = size - 1; i >= 0; i--)
      System.out.println(v[i]);
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }
  
}

// il est plus propre de séparer le code qui réalise le tableau
// redimensionnable (ici dans une classe ResizableArray) du code
// qui l'utilise (ici Amphi1myvectorclass juste en-dessous)

class ResizableArray {
  private String[] elts;
  private int size;
  
  ResizableArray() {
    this.elts = new String[10];
    this.size = 0;
  }
  
  int size() { return this.size; }
  
  void add(String s) {
    if (this.size == this.elts.length) {
      String[] old = this.elts;
      this.elts = new String[2 * this.size];
      System.arraycopy(old, 0, this.elts, 0, this.size);
    }
    this.elts[this.size++] = s;
  }
  
  String get(int i) { return this.elts[i]; }
  
}

class Amphi1myvectorclass {
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    double start = System.currentTimeMillis();
    ResizableArray ra = new ResizableArray();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      ra.add(s);
    }
    for (int i = ra.size() - 1; i >= 0; i--)
      System.out.println(ra.get(i));
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }
  
}

// solution utilisant les listes de la bibliothèque (LinkedList)
// complexité linéaire, mais un peu plus coûteux que Vector au final

class Amphi1list {
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    LinkedList<String> l = new LinkedList<String>();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      l.addFirst(s);
    }
    for (String s : l)
      System.out.println(s);
  }
  
}

// la même chose, mais cette fois avec des listes que l'on écrit soi-même
// (des listes simplement chaînées, cette fois, car cela suffit)

class Singly {
  String element;
  Singly next;
  
  public Singly(String element, Singly next) {
    this.element = element;
    this.next = next;
  }
}

class Amphi1mylist {
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    Singly l = null;
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      l = new Singly(s, l);
    }
    while (l != null) {
      System.out.println(l.element);
      l = l.next;
    }
  }
  
}

// là encore, on peut séparer le code manipulant les listes
// du reste du code ; on le fait ici dans une classe MyStack
// qui réalise une structure de pile

class MyStack {
  private Singly top;

  MyStack() {
    this.top = null;
  }

  boolean isEmpty() {
    return this.top == null;
  }

  void add(String s) {
    this.top = new Singly(s, this.top);
  }

  String pop() {
    if (this.isEmpty()) throw new NoSuchElementException();
    String r = this.top.element;
    this.top = this.top.next;
    return r;
  }
}

class Amphi1mystack {
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    MyStack st = new MyStack();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      st.add(s);
    }
    while (!st.isEmpty())
      System.out.println(st.pop());
  }
  
}

// la structure de pile existe déjà dans la biliothèque Java
// (c'est Stack) et on l'utilise ici

class Amphi1stack {
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    Stack<String> st = new Stack<String>();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      st.add(s);
    }
    while (!st.isEmpty())
      System.out.println(st.pop());
  }
  
}

// enfin, une solution récursive
// mais elle a l'inconvénient de faire débordement la pile assez rapidement
// (quelques dizaines de milliers de lignes)
// si besoin, on peut augmenter la taille de pile avec l'option -Xss de
// la machine virtuelle Java

class Amphi1rec {
  
  private static void read(BufferedReader r) throws IOException {
    String s = r.readLine();
    if (s == null) return;
    read(r);
    System.out.println(s);
  }
  
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    read(r);
  }
  
}