import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Random;
import java.util.Collection;

class NutsAndBolts {
    /**
     * Given a set of bolts and an equally large set of nuts,
     * where for each bolt there is a exactly one fitting nut,
     * this algorithm finds a corresponding nut for every bolt.
     * We cannot compare the sizes of two bolts or two nuts,
     * the only thing we can do is to tell whether the nut is
     * too big for the bolt or too small.
     *
     * The algorithm runs in O(NlgN) time and
     * requires O(N) additional space (to copy the contents of
     * the `nuts` and `bolts` lists.
     */
    static <T extends Comparable<T>> List<Pair<Nut<T>, Bolt<T>>>
            pairNutsAndBolts(Collection<Nut<T>> nuts,
            Collection<Bolt<T>> bolts) {
        if (nuts.size() != bolts.size()) {
            throw new IllegalArgumentException(String.format(
                "Expected: same amount of nuts as bolts"
                + " Got: len(nuts) = %d, len(bolts) = %d",
                nuts.size(), bolts.size()
            ));
        }

        List<Nut<T>> copyNuts = new ArrayList<>(nuts);
        List<Bolt<T>> copyBolts = new ArrayList<>(bolts);
        
        Random random = new Random();
        shuffle(copyNuts, random);
        shuffle(copyBolts, random);

        List<Pair<Nut<T>, Bolt<T>>> list =
            new LinkedList<Pair<Nut<T>, Bolt<T>>>();
        pairNutsAndBolts(list, copyNuts, copyBolts, 0, nuts.size()); 
        return list;
    }

    private static <T extends Comparable<T>> void pairNutsAndBolts(
            List<Pair<Nut<T>, Bolt<T>>> list,
            List<Nut<T>> nuts, List<Bolt<T>> bolts, int lo, int hi) {
        if (hi - lo == 1) {
            list.add(new Pair<>(nuts.get(lo), bolts.get(lo)));
        } else if (hi - lo > 1) {
            int mid = partition(nuts, bolts.get(lo), lo, hi);
            partition(bolts, nuts.get(mid), lo, hi);
            list.add(new Pair<>(nuts.get(mid), bolts.get(mid)));

            pairNutsAndBolts(list, nuts, bolts, lo, mid);
            pairNutsAndBolts(list, nuts, bolts, mid + 1, hi);
        }
    }

    private static <T extends Comparable<U>, U> int partition(
            List<T> array, U pivot, int lo, int hi) {
        for (int i = lo; i < hi; i++) {
            if (array.get(i).compareTo(pivot) == 0) {
                swap(array, lo, i);
                break;
            }
        }
        int iLeft = lo, iRight = hi;
        do {
            iLeft++;
            while (iLeft < hi - 1
                    && array.get(iLeft).compareTo(pivot) < 0) {
                iLeft++;
            }
            iRight--;
            while (iRight > lo
                    && array.get(iRight).compareTo(pivot) > 0) {
                iRight--;
            }
            if (iLeft < iRight) {
                swap(array, iLeft, iRight);
            }
        }
        while (iLeft < iRight);

        swap(array, lo, iRight);
        return iRight;
    }

    private static <T> void shuffle(List<T> array, Random random) {
        final int n = array.size();
        for (int i = 0; i < n - 1; i++) {
            swap(array, i, i + random.nextInt(n - i - 1) + 1);
        }
    }

    private static <T> void swap(List<T> array, int i, int j) {
        assert i >= 0 && j >= 0
            && i < array.size() && j < array.size();

        T temp = array.get(i);
        array.set(i, array.get(j));
        array.set(j, temp);
    }

    static class Nut<T extends Comparable<T>>
            implements Comparable<Bolt<T>> {
        private T value; 

        public Nut(T value) {
            this.value = value;
        }

        @Override
        public int compareTo(Bolt<T> bolt) {
            return this.value.compareTo(bolt.value);
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }

    static class Bolt<T extends Comparable<T>> 
            implements Comparable<Nut<T>> {
        T value;

        public Bolt(T value) {
            this.value = value;
        }

        @Override
        public int compareTo(Nut<T> nut) {
            return this.value.compareTo(nut.value);
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }

    static class Pair<T, U> {
        private T first;
        private U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        public T getFirst() {
            return first;
        }

        public U getSecond() {
            return second;
        }

        @Override
        public String toString() {
            return String.format("(%s, %s)", first, second);
        }
    }
    
    public static void main(String[] args) {
        List<Nut<Integer>> nuts = new ArrayList<>();
        List<Bolt<Integer>> bolts = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            nuts.add(new Nut<>(i));
            bolts.add(new Bolt<>(9 - i));
        }
        for (Pair<Nut<Integer>, Bolt<Integer>> pair
                : pairNutsAndBolts(nuts, bolts)) {
            System.out.println(pair);
        }
    }
}