// sort in Java
// library (Collections) ArrayList version written Jan 01 by Ulrich Stern

import java.util.*;

public class sort_library_ArrayList {

  static class Range {
    int lb;
    int ub;
    Range(int l, int u) {
      lb = l;  ub = u;
    }
    public String toString() {
      return "[" + lb + "," + ub + "]";
    }
  }

  // compare lower bound
  static class LBComparator implements Comparator {
    public int compare(Object o1, Object o2) {
      return ((Range)o1).lb - ((Range)o2).lb;
    }
  }

  // compare upper bound
  static class UBComparator implements Comparator {
    public int compare(Object o1, Object o2) {
      return ((Range)o1).ub - ((Range)o2).ub;
    }
  }
      
  public static void main(String[] args) {
    final int N = 2000000;
    List a = new ArrayList(N);
    for (int i=0; i<N; i++)
      a.add(i, new Range(i*7%1000, i*13%1000));

    System.out.println("sorting...");

    Collections.sort(a, new LBComparator());
    Collections.sort(a, new UBComparator());

    System.out.println("done.");
  }
}