Cuckoo for Hashing

An integer hash table is a data structure that supports insert, delete and lookup of integer values in constant time. A traditional hash structure consists of an array of size $n$ (the hash table) and a hash function $f(x)$, which is usually $f(x) = x \bmod n$. To insert a value $x$ into the table, you compute its hash value $f(x)$, which is the index of the location where $x$ goes. For example, if $x = 1234$ and the hash table has size $101$, then $1234$ goes into location $22 = 1234 \bmod 101$. Of course, some other value may already sit in that location ($x = 22$, for example), which is a collision. Collisions can be handled in several ways, none of which this problem deals with.

Cuckoo hashing uses two hash tables $T_1$ and $T_2$, each with its own hash function $f_1(x)$ and $f_2(x)$. Insertion of a value $x$ proceeds as follows. You first try to store $x$ in $T_1$ at location $f_1(x)$. If that location is empty, store $x$ there and the insertion is done. Otherwise there is a collision to handle. Let $y$ be the value currently in that location. You replace $y$ with $x$ in $T_1$, then try to store $y$ in $T_2$ at location $f_2(y)$. Again, if that location is empty, you store $y$ there and the insertion is done. Otherwise you replace the value there (call it $z$) with $y$, and try to store $z$ back in $T_1$ at location $f_1(z)$, and so on. The process bounces back and forth between the two tables until an empty location turns up. A real implementation rehashes both tables once a certain number of swaps have occurred, but that never happens in this problem: every insertion is guaranteed to find an empty location.

Given the sizes of the two tables and a series of insertions, determine what each table holds at the end.

The name comes from the cuckoo bird, which lays its eggs in another bird's nest. The larger cuckoo chick hatches first and pushes the other chicks out of the nest, so it gets all the food. Gruesome but efficient.

The input holds several test cases. Each test case starts with three positive integers $n_1$, $n_2$ and $m$, where $n_1$ and $n_2$ are the sizes of tables $T_1$ and $T_2$, and $m$ is the number of insertions. The $m$ values to insert follow, in insertion order, and all of them are non-negative. Both tables start empty, and table $T_i$ uses the hash function $f_i(x) = x \bmod n_i$. A line containing three zeros ends the input and is not a test case.

Constraints: $1 \le n_1, n_2 \le 1000$, $n_1 \ne n_2$

For each test case, print Case k: on its own line, where $k$ counts the test cases starting at 1. Then, if $T_1$ holds at least one value, print Table 1 on its own line, followed by the non-empty locations of $T_1$ from the lowest index to the highest, one per line, in the form i:v, where $i$ is the index of the location and $v$ is the value stored there. Print Table 2 and the non-empty locations of $T_2$ the same way. If a table is empty, print nothing for it, not even its header.