static class Echiquier {
    Chainon premier;
    Chainon suivant;
   
    static class Chainon {
      int ligne;
      int colonne;
      Chainon suivant;
      }

/*
        * Le plus rapide tri que j'ai vue jusqu'ici...
        * un quicksort amélioré avec trimedian et insertionsort.
        */
       
        public class SortingAlgo {
                /*
                * seul méthodes utilisable par l'utilisateur de la classe.
                */
                public static int[] quickSort(int[] items) {
                        time = System.nanoTime();
                        items = quickSort(items, 0, items.length-1);
                        items = insertionSort(items,0,items.length-1);
                        time = System.nanoTime() - time;
                        return items;
        }
           
           public static int nanoTimeTaken() {
                   return (int)time;
                }
           
                /**********************************************************************/
                private static int[] quickSort(int[] a,int l,int r) {
                        int M = 4;
              int i;
              int j;
              int v;
       
              if ((r-l)>M) {
                  i = (r+l)/2;
                  if (a[l]>a[i]) swap(a,l,i);     // Tri-Median Methode!
                  if (a[l]>a[r]) swap(a,l,r);
                  if (a[i]>a[r]) swap(a,i,r);
       
                  j = r-1;
                  swap(a,i,j);
                  i = l;
                  v = a[j];
                  for(;;) {
                 while(a[++i]<v);
                 while(a[--j]>v);
                 if (j<i) break;
                 swap (a,i,j);
                  }
                  swap(a,i,r-1);
                  quickSort(a,l,j);
                  quickSort(a,i+1,r);
              }
              return a;
           }
           private static int[] swap(int a[], int i, int j) {
          int T;
          T = a[i];
          a[i] = a[j];
          a[j] = T;
          return a;
        }
                private static int[] insertionSort(int a[], int lo0, int hi0) {
          int i;
          int j;
          int v;
          for (i=lo0+1;i<=hi0;i++){
               v = a[i];
               j=i;
               while ((j>lo0) && (a[j-1]>v)){
                    a[j] = a[j-1];
                    j--;
               }
               a[j] = v;
          }
          return a;
           }
           private static long time = 0;
         }