Two players play the following game. Initially, the players have a knife and a rectangular sheet of paper, divided into equal square grid cells of unit size. The players make moves in turn, the player who can't make a move loses. In one move, a player can take the knife and cut the paper along any segment of the grid line (not necessarily from border to border). The part of the paper, that touches the knife at least once, is considered cut. There is one limit not to turn the game into an infinite cycle: each move has to cut the paper, that is the knife has to touch the part of the paper that is not cut before.

Obviously, the game ends when the entire sheet is cut into 1 × 1 blocks. During the game, the pieces of the sheet are not allowed to move. It is also prohibited to cut along the border. The coordinates of the ends of each cut must be integers.

You are given an n × m piece of paper, somebody has already made k cuts there. Your task is to determine who will win if the players start to play on this sheet. You can consider that both players play optimally well. If the first player wins, you also need to find the winning first move.

Input

The first line contains three integers n, m, k (1 ≤ n, m ≤ 109, 0 ≤ k ≤ 105) — the sizes of the piece of paper and the number of cuts. Then follow k lines, each containing 4 integers xbi, ybi, xei, yei (0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m) — the coordinates of the ends of the existing cuts. 

It is guaranteed that each cut has a non-zero length, is either vertical or horizontal and doesn't go along the sheet border.

The cuts may intersect, overlap and even be the same. That is, it is not guaranteed that the cuts were obtained during any correct game.

Output

If the second player wins, print "SECOND". Otherwise, in the first line print "FIRST", and in the second line print any winning move of the first player (the coordinates of the cut ends, follow input format to print them).

Examples

Input

2 1 0


Output

FIRST
1 0 1 1


Input

2 2 4
0 1 2 1
0 1 2 1
1 2 1 0
1 1 1 2


Output

SECOND
2 2 1
0 1 1 1
 5 5 20
3 1 3 3
1 2 2 2
4 3 4 2
3 2 2 2
3 4 2 4
4 1 4 5
4 3 5 3
5 1 0 1
0 1 5 1
3 5 3 1
3 1 3 2
1 5 1 0
3 4 3 3
3 3 3 4
1 3 3 3
2 5 2 1
0 2 1 2
2 1 0 1
4 3 5 3
1 4 1 5
 5 5 46
3 5 3 1
2 1 2 0
1 2 1 0
4 1 0 1
4 3 4 1
0 4 5 4
3 0 3 4
3 2 0 2
4 5 4 3
4 1 3 1
1 4 1 1
1 1 2 1
3 2 1 2
3 2 3 4
2 0 2 2
1 0 1 2
1 1 4 1
0 4 3 4
3 0 3 3
3 1 3 4
5 1 3 1
3 0 3 5
4 1 1 1
2 5 2 3
4 2 4 1
1 3 1 5
1 2 1 4
4 2 4 1
3 2 3 0
0 4 3 4
1 3 2 3
4 5 4 3
1 2 1 1
4 3 3 3
2 0 2 1
3 0 3 2
3 1 3 0
2 4 2 0
2 5 2 3
1 3 1 2
0 2 5 2
0 4 2 4
3 4 3 2
4 3 4 2
4 2 3 2
2 1 1 1
 5 5 17
4 4 4 1
3 2 1 2
1 3 3 3
4 4 4 3
4 4 4 5
5 4 4 4
5 3 2 3
1 5 1 4
4 0 4 4
2 3 2 4
1 0 1 5
3 2 3 0
3 1 4 1
1 4 4 4
1 2 1 1
3 1 3 5
1 3 4 3
 2 2 0
 1000000000 1000000000 0
 5 5 3
1 2 1 0
0 2 3 2
2 1 0 1
 999999999 999999999 0
 5 5 44
4 0 4 4
4 4 4 1
3 0 3 4
1 5 1 4
1 4 1 1
1 5 1 4
4 4 4 5
2 0 2 2
1 2 0 2
1 1 1 0
1 1 2 1
2 1 2 0
4 3 4 0
4 4 4 3
1 0 1 5
1 4 3 4
1 2 1 3
4 2 1 2
3 1 3 3
0 1 3 1
2 1 0 1
0 3 1 3
5 1 2 1
4 4 4 5
1 3 1 0
4 3 0 3
5 2 2 2
2 2 0 2
1 1 0 1
3 4 2 4
1 5 1 1
4 3 4 1
2 3 2 5
1 3 1 5
3 4 3 5
1 2 4 2
4 4 4 3
3 3 2 3
4 0 4 4
3 5 3 4
0 2 1 2
3 0 3 1
4 0 4 3
3 4 1 4
 1 2 1
0 1 1 1
 1 1 0
 3 4 2
1 0 1 4
2 0 2 4
 5 5 42
4 2 1 2
2 4 2 3
3 4 5 4
3 5 3 4
3 4 3 1
1 4 1 0
3 3 3 4
3 3 4 3
1 4 1 5
2 2 4 2
1 2 1 5
5 2 1 2
4 2 3 2
4 3 2 3
5 4 3 4
3 1 3 4
2 1 2 3
1 1 1 5
1 0 1 4
4 4 4 1
4 1 1 1
4 4 0 4
1 3 1 0
4 3 4 5
2 3 2 5
2 5 2 4
1 3 1 0
3 4 3 3
3 1 4 1
3 4 5 4
2 2 2 0
2 0 2 4
0 1 5 1
3 2 3 0
5 2 4 2
1 4 4 4
2 2 2 0
4 4 5 4
2 2 2 3
2 3 2 2
4 1 0 1
3 3 3 2
 1 1000000000 0
 5 5 10
4 3 4 0
3 5 3 4
2 4 2 3
3 3 3 0
4 4 5 4
1 2 0 2
4 3 1 3
1 1 1 3
2 3 4 3
4 1 1 1
 4 4 10
3 0 3 1
2 1 4 1
1 1 2 1
3 1 2 1
3 1 2 1
3 3 4 3
2 3 2 0
4 2 0 2
3 2 2 2
2 2 2 1
 5 5 2
4 3 4 0
5 4 1 4
 1000000000 999999999 1
314159265 0 314159265 999999999
 4 3 10
1 0 1 1
0 1 1 1
0 2 1 2
1 3 1 2
2 0 2 1
2 3 2 2
4 1 3 1
3 0 3 1
4 2 3 2
3 3 3 2
 5 5 19
4 0 4 1
3 2 2 2
0 3 3 3
4 1 4 0
5 4 2 4
2 5 2 0
5 3 2 3
5 1 4 1
4 0 4 5
1 4 5 4
3 0 3 1
2 1 2 3
1 1 1 3
2 2 2 0
4 5 4 1
0 3 5 3
5 3 1 3
3 2 3 4
5 1 1 1
 10 11 13
0 4 1 4
2 8 2 10
10 4 5 4
2 4 10 4
9 6 8 6
10 9 7 9
3 2 3 1
1 8 1 0
2 10 2 5
8 1 1 1
10 3 3 3
7 10 3 10
2 1 2 4
 1000000000 999999999 0
 4 1 0
 5 5 38
4 5 4 4
5 1 0 1
0 2 2 2
4 3 2 3
5 3 1 3
2 2 2 4
1 2 0 2
0 2 4 2
3 3 3 2
3 1 3 0
4 3 3 3
0 1 1 1
2 4 2 5
2 5 2 2
1 3 1 0
2 5 2 1
5 2 1 2
0 1 4 1
2 4 3 4
3 3 4 3
2 3 2 0
2 3 2 5
1 3 3 3
4 1 2 1
4 3 4 2
3 1 5 1
4 4 4 2
0 2 1 2
2 2 2 5
4 2 4 3
3 3 2 3
4 0 4 5
4 2 0 2
3 1 3 3
2 5 2 0
1 1 1 0
1 3 2 3
4 0 4 3
 5 5 0

FIRST
1 0 1 1
 FIRST
0 4 4 4
 FIRST
0 3 3 3
 FIRST
0 2 5 2
 SECOND
 SECOND
 FIRST
2 0 2 3
 SECOND
 FIRST
0 4 5 4
 SECOND
 SECOND
 FIRST
0 1 3 1
 FIRST
0 3 5 3
 FIRST
0 1 1 1
 FIRST
2 0 2 5
 FIRST
1 0 1 4
 FIRST
4 0 4 4
 SECOND
 FIRST
1 0 1 2
 FIRST
0 2 4 2
 FIRST
1 0 1 11
 FIRST
1 0 1 999999999
 FIRST
1 0 1 1
 FIRST
0 4 4 4
 SECOND

import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.util.Collection;
import java.util.Map;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Set;
import java.util.AbstractMap;
import java.util.NoSuchElementException;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Egor Kulikov (egor@egork.net)
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
		int rowCount = in.readInt();
		int columnCount = in.readInt();
		int cutCount = in.readInt();
		final int[] x0 = new int[cutCount];
		final int[] y0 = new int[cutCount];
		final int[] x1 = new int[cutCount];
		final int[] y1 = new int[cutCount];
		IOUtils.readIntArrays(in, x0, y0, x1, y1);
		Map<Integer, IntList> horizontal = new CPPMap<Integer, IntList>(new Factory<IntList>() {
			public IntList create() {
				return new IntArrayList();
			}
		});
		Map<Integer, IntList> vertical = new CPPMap<Integer, IntList>(new Factory<IntList>() {
			public IntList create() {
				return new IntArrayList();
			}
		});
		for (int i = 0; i < cutCount; i++) {
			if (x0[i] == x1[i])
				horizontal.get(x0[i]).add(i);
			else
				vertical.get(y0[i]).add(i);
		}
		Map<Integer, Integer> horizontalQty = new EHashMap<Integer, Integer>();
		Map<Integer, Integer> verticalQty = new EHashMap<Integer, Integer>();
		for (Map.Entry<Integer, IntList> entry : horizontal.entrySet()) {
			entry.getValue().inPlaceSort(new IntComparator() {
				public int compare(int first, int second) {
					return Math.min(y0[first], y1[first]) - Math.min(y0[second], y1[second]);
				}
			});
			int end = 0;
			int qty = 0;
			for (int i : entry.getValue().toArray()) {
				int curStart = Math.min(y0[i], y1[i]);
				if (curStart > end)
					qty += curStart - end;
				end = Math.max(end, Math.max(y0[i], y1[i]));
			}
			qty += columnCount - end;
			horizontalQty.put(entry.getKey(), qty);
		}
		for (Map.Entry<Integer, IntList> entry : vertical.entrySet()) {
			entry.getValue().inPlaceSort(new IntComparator() {
				public int compare(int first, int second) {
					return Math.min(x0[first], x1[first]) - Math.min(x0[second], x1[second]);
				}
			});
			int end = 0;
			int qty = 0;
			for (int i : entry.getValue().toArray()) {
				int curStart = Math.min(x0[i], x1[i]);
				if (curStart > end)
					qty += curStart - end;
				end = Math.max(end, Math.max(x0[i], x1[i]));
			}
			qty += rowCount - end;
			verticalQty.put(entry.getKey(), qty);
		}
		int nimber = 0;
		for (int i : horizontalQty.values())
			nimber ^= i;
		for (int i : verticalQty.values())
			nimber ^= i;
		nimber ^= columnCount * ((rowCount - horizontalQty.size() - 1) & 1);
		nimber ^= rowCount * ((columnCount - verticalQty.size() - 1) & 1);
		if (nimber == 0) {
			out.printLine("SECOND");
			return;
		}
		out.printLine("FIRST");
		for (int i = 1; i < rowCount; i++) {
			if (!horizontalQty.containsKey(i)) {
				horizontalQty.put(i, columnCount);
				break;
			}
		}
		for (int i = 1; i < columnCount; i++) {
			if (!verticalQty.containsKey(i)) {
				verticalQty.put(i, rowCount);
				break;
			}
		}
		for (Map.Entry<Integer, Integer> entry : horizontalQty.entrySet()) {
			if ((nimber ^ entry.getValue()) <= entry.getValue()) {
				int remaining = entry.getValue() - (nimber ^ entry.getValue());
				int end = 0;
				for (int i : horizontal.get(entry.getKey()).toArray()) {
					int curStart = Math.min(y0[i], y1[i]);
					if (curStart > end) {
						if (remaining <= curStart - end) {
							out.printLine(entry.getKey(), 0, entry.getKey(), end + remaining);
							return;
						}
						remaining -= curStart - end;
					}
					end = Math.max(end, Math.max(y0[i], y1[i]));
				}
				out.printLine(entry.getKey(), 0, entry.getKey(), end + remaining);
				return;
			}
		}
		for (Map.Entry<Integer, Integer> entry : verticalQty.entrySet()) {
			if ((nimber ^ entry.getValue()) <= entry.getValue()) {
				int remaining = entry.getValue() - (nimber ^ entry.getValue());
				int end = 0;
				for (int i : vertical.get(entry.getKey()).toArray()) {
					int curStart = Math.min(x0[i], x1[i]);
					if (curStart > end) {
						if (remaining <= curStart - end) {
							out.printLine(0, entry.getKey(), end + remaining, entry.getKey());
							return;
						}
						remaining -= curStart - end;
					}
					end = Math.max(end, Math.max(x0[i], x1[i]));
				}
				out.printLine(0, entry.getKey(), end + remaining, entry.getKey());
				return;
			}
		}
    }
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	public static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

    public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	}

class IOUtils {

	public static void readIntArrays(InputReader in, int[]... arrays) {
		for (int i = 0; i < arrays[0].length; i++) {
			for (int j = 0; j < arrays.length; j++)
				arrays[j][i] = in.readInt();
		}
	}

	}

abstract class IntList extends IntCollection {
	private static final int INSERTION_THRESHOLD = 8;

	public abstract int get(int index);
	public abstract void set(int index, int value);

	public IntIterator iterator() {
		return new IntIterator() {
			private int size = size();
			private int index = 0;

			public int value() throws NoSuchElementException {
				if (!isValid())
					throw new NoSuchElementException();
				return get(index);
			}

			public void advance() throws NoSuchElementException {
				if (!isValid())
					throw new NoSuchElementException();
				index++;
			}

			public boolean isValid() {
				return index < size;
			}
		};
	}

	private void swap(int first, int second) {
		if (first == second)
			return;
		int temp = get(first);
		set(first, get(second));
		set(second, temp);
	}

	public IntSortedList inPlaceSort(IntComparator comparator) {
		quickSort(0, size() - 1, size(), comparator);
		return new IntSortedArray(this, comparator);
	}

	private void quickSort(int from, int to, int remaining, IntComparator comparator) {
		if (to - from < INSERTION_THRESHOLD) {
			insertionSort(from, to, comparator);
			return;
		}
		if (remaining == 0) {
			heapSort(from, to, comparator);
			return;
		}
		remaining >>= 1;
		int pivotIndex = (from + to) >> 1;
		int pivot = get(pivotIndex);
		swap(pivotIndex, to);
		int storeIndex = from;
		int equalIndex = to;
		for (int i = from; i < equalIndex; i++) {
			int value = comparator.compare(get(i), pivot);
			if (value < 0)
				swap(storeIndex++, i);
			else if (value == 0)
				swap(--equalIndex, i--);
		}
		quickSort(from, storeIndex - 1, remaining, comparator);
		for (int i = equalIndex; i <= to; i++)
			swap(storeIndex++, i);
		quickSort(storeIndex, to, remaining, comparator);
	}

	private void heapSort(int from, int to, IntComparator comparator) {
		for (int i = (to + from - 1) >> 1; i >= from; i--)
			siftDown(i, to, comparator, from);
		for (int i = to; i > from; i--) {
			swap(from, i);
			siftDown(from, i - 1, comparator, from);
		}
	}

	private void siftDown(int start, int end, IntComparator comparator, int delta) {
		int value = get(start);
		while (true) {
			int child = ((start - delta) << 1) + 1 + delta;
			if (child > end)
				return;
			int childValue = get(child);
			if (child + 1 <= end) {
				int otherValue = get(child + 1);
				if (comparator.compare(otherValue, childValue) > 0) {
					child++;
					childValue = otherValue;
				}
			}
			if (comparator.compare(value, childValue) >= 0)
				return;
			swap(start, child);
			start = child;
		}
	}

	private void insertionSort(int from, int to, IntComparator comparator) {
		for (int i = from + 1; i <= to; i++) {
			int value = get(i);
			for (int j = i - 1; j >= from; j--) {
				if (comparator.compare(get(j), value) <= 0)
					break;
				swap(j, j + 1);
			}
		}
	}

	public IntSortedList sort(IntComparator comparator) {
		return new IntArray(this).inPlaceSort(comparator);
	}

	}

class CPPMap<K, V> extends EHashMap<K, V> {
	private final Factory<V> defaultValueFactory;

	public CPPMap(Factory<V> defaultValueFactory) {
		this.defaultValueFactory = defaultValueFactory;
	}

	public V get(Object key) {
		if (containsKey(key))
			return super.get(key);
		V value = defaultValueFactory.create();
		try {
			//noinspection unchecked
			super.put((K) key, value);
			return value;
		} catch (ClassCastException e) {
			return value;
		}
	}
}

interface Factory<V> {
	public V create();
}

class IntArrayList extends IntList {
	private int[] array;
	private int size;

	public IntArrayList() {
		this(10);
	}

	public IntArrayList(int capacity) {
		array = new int[capacity];
	}

	public int get(int index) {
		if (index >= size)
			throw new IndexOutOfBoundsException();
		return array[index];
	}

	public void set(int index, int value) {
		if (index >= size)
			throw new IndexOutOfBoundsException();
		array[index] = value;
	}

	public int size() {
		return size;
	}

	public void add(int value) {
		ensureCapacity(size + 1);
		array[size++] = value;
	}

	private void ensureCapacity(int newCapacity) {
		if (newCapacity > array.length) {
			int[] newArray = new int[Math.max(newCapacity, array.length << 1)];
			System.arraycopy(array, 0, newArray, 0, size);
			array = newArray;
		}
	}

	public int[] toArray() {
		int[] array = new int[size];
		System.arraycopy(this.array, 0, array, 0, size);
		return array;
	}

    }

abstract class IntCollection {
	public abstract IntIterator iterator();
	public abstract int size();
	public abstract void add(int value);

	public int[] toArray() {
		int size = size();
		int[] array = new int[size];
		int i = 0;
		for (IntIterator iterator = iterator(); iterator.isValid(); iterator.advance())
			array[i++] = iterator.value();
		return array;
	}

	}

class EHashMap<E, V> extends AbstractMap<E, V> {
	private static final int[] shifts = new int[10];

	private int size;
	private HashEntry<E, V>[] data;
	private int capacity;
	private Set<Entry<E, V>> entrySet;

	static {
		Random random = new Random(System.currentTimeMillis());
		for (int i = 0; i < 10; i++)
			shifts[i] = 1 + 3 * i + random.nextInt(3);
	}

	public EHashMap() {
		this(4);
	}

	private void setCapacity(int size) {
		capacity = Integer.highestOneBit(4 * size);
        //noinspection unchecked
        data = new HashEntry[capacity];
	}

	public EHashMap(int maxSize) {
		setCapacity(maxSize);
		entrySet = new AbstractSet<Entry<E, V>>() {
			@Override
			public Iterator<Entry<E, V>> iterator() {
				return new Iterator<Entry<E, V>>() {
					private HashEntry<E, V> last = null;
                    private HashEntry<E, V> current = null;
                    private HashEntry<E, V> base = null;
                    private int lastIndex = -1;
					private int index = -1;

					public boolean hasNext() {
                        if (current == null) {
                            for (index++; index < capacity; index++) {
                                if (data[index] != null) {
                                    base = current = data[index];
                                    break;
                                }
                            }
                        }
                        return current != null;
					}

					public Entry<E, V> next() {
						if (!hasNext())
							throw new NoSuchElementException();
                        last = current;
                        lastIndex = index;
                        current = current.next;
                        if (base.next != last)
                            base = base.next;
						return last;
					}

					public void remove() {
						if (last == null)
							throw new IllegalStateException();
                        size--;
                        if (base == last)
                            data[lastIndex] = last.next;
                        else
                            base.next = last.next;
					}
				};
			}

			@Override
			public int size() {
				return size;
			}
		};
	}

	public EHashMap(Map<E, V> map) {
		this(map.size());
		putAll(map);
	}

	public Set<Entry<E, V>> entrySet() {
		return entrySet;
	}

	public void clear() {
		Arrays.fill(data, null);
		size = 0;
	}

	private int index(Object o) {
		return getHash(o.hashCode()) & (capacity - 1);
	}

	private int getHash(int h) {
		int result = h;
		for (int i : shifts)
			result ^= h >>> i;
		return result;
	}

	public V remove(Object o) {
		if (o == null)
			return null;
		int index = index(o);
        HashEntry<E, V> current = data[index];
        HashEntry<E, V> last = null;
        while (current != null) {
            if (current.key.equals(o)) {
                if (last == null)
                    data[index] = current.next;
                else
                    last.next = current.next;
                size--;
                return current.value;
            }
            last = current;
            current = current.next;
        }
        return null;
	}

	public V put(E e, V value) {
		if (e == null)
			return null;
		int index = index(e);
        HashEntry<E, V> current = data[index];
        if (current != null) {
            while (true) {
                if (current.key.equals(e)) {
                    V oldValue = current.value;
                    current.value = value;
                    return oldValue;
                }
                if (current.next == null)
                    break;
                current = current.next;
            }
        }
        if (current == null)
            data[index] = new HashEntry<E, V>(e, value);
        else
            current.next = new HashEntry<E, V>(e, value);
        size++;
        if (2 * size > capacity) {
            HashEntry<E, V>[] oldData = data;
            setCapacity(size);
            for (HashEntry<E, V> entry : oldData) {
                while (entry != null) {
                    HashEntry<E, V> next = entry.next;
                    index = index(entry.key);
                    entry.next = data[index];
                    data[index] = entry;
                    entry = next;
                }
            }
        }
		return null;
	}

	public V get(Object o) {
		if (o == null)
			return null;
		int index = index(o);
        HashEntry<E, V> current = data[index];
		while (current != null) {
			if (current.key.equals(o))
                return current.value;
            current = current.next;
        }
		return null;
	}

	public boolean containsKey(Object o) {
        if (o == null)
            return false;
        int index = index(o);
        HashEntry<E, V> current = data[index];
        while (current != null) {
            if (current.key.equals(o))
                return true;
            current = current.next;
        }
        return false;
	}

	public int size() {
		return size;
	}

	private static class HashEntry<E, V> implements Entry<E, V> {
		private final E key;
		private V value;
        private HashEntry<E, V> next;

        private HashEntry(E key, V value) {
            this.key = key;
            this.value = value;
        }


        public E getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
    }
}

abstract class IntSortedList extends IntList {
	protected final IntComparator comparator;

	protected IntSortedList(IntComparator comparator) {
		this.comparator = comparator;
	}

	public void set(int index, int value) {
		throw new UnsupportedOperationException();
	}

	public void add(int value) {
		throw new UnsupportedOperationException();
	}

	public IntSortedList inPlaceSort(IntComparator comparator) {
		if (comparator == this.comparator)
			return this;
		throw new UnsupportedOperationException();
	}

	public IntSortedList sort(IntComparator comparator) {
		if (comparator == this.comparator)
			return this;
		return super.sort(comparator);
	}

	protected void ensureSorted() {
		int size = size();
		if (size == 0)
			return;
		int last = get(0);
		for (int i = 1; i < size; i++) {
			int current = get(i);
			if (comparator.compare(last, current) > 0)
				throw new IllegalArgumentException();
			last = current;
		}
	}

	}

interface IntComparator {
    public static final IntComparator DEFAULT = new IntComparator() {
        public int compare(int first, int second) {
            if (first < second)
                return -1;
            if (first > second)
                return 1;
            return 0;
        }
    };

	public int compare(int first, int second);
}

interface IntIterator {
	public int value() throws NoSuchElementException;
	/*
	 * @throws NoSuchElementException only if iterator already invalid
	 */
	public void advance() throws NoSuchElementException;
	public boolean isValid();
}

class IntSortedArray extends IntSortedList {
	private final int[] array;

	public IntSortedArray(int[] array) {
		this(array, IntComparator.DEFAULT);
	}

	public IntSortedArray(IntCollection collection) {
		this(collection, IntComparator.DEFAULT);
	}

	public IntSortedArray(int[] array, IntComparator comparator) {
		super(comparator);
		this.array = array;
		ensureSorted();
	}

	public IntSortedArray(IntCollection collection, IntComparator comparator) {
		super(comparator);
		array = new int[collection.size()];
		int i = 0;
		for (IntIterator iterator = collection.iterator(); iterator.isValid(); iterator.advance())
			array[i++] = iterator.value();
		ensureSorted();
	}

	public int get(int index) {
		return array[index];
	}

	public int size() {
		return array.length;
	}
}

class IntArray extends IntList {
	private final int[] array;

	public IntArray(int[] array) {
		this.array = array;
	}

	public IntArray(IntCollection collection) {
		array = new int[collection.size()];
		int i = 0;
		for (IntIterator iterator = collection.iterator(); iterator.isValid(); iterator.advance())
			array[i++] = iterator.value();
	}

	public int get(int index) {
		return array[index];
	}

	public void set(int index, int value) {
		array[index] = value;
	}

	public int size() {
		return array.length;
	}

	public void add(int value) {
		throw new UnsupportedOperationException();
	}

	public int[] toArray() {
		return array;
	}
}

