쿠쿠 해싱

정수 해시 테이블은 정수의 삽입, 삭제, 조회를 상수 시간에 지원하는 자료구조다. 전통적인 해시 구조는 크기가 $n$인 배열 하나와 해시 함수 $f(x)$로 이루어지고, 해시 함수로는 보통 $f(x) = x \bmod n$을 쓴다. 값 $x$를 넣을 때는 해시값 $f(x)$를 계산해 그 번호의 칸에 $x$를 저장한다. 예를 들어 $x = 1234$이고 테이블 크기가 $101$이면 $1234$는 $22 = 1234 \bmod 101$번 칸에 들어간다. 물론 그 칸에 이미 다른 값이(예를 들어 $x = 22$) 들어 있을 수 있고, 이것을 충돌이라고 한다. 충돌을 처리하는 방법은 여러 가지지만 이 문제에서는 다루지 않는다.

쿠쿠 해싱은 해시 테이블 두 개 $T_1$과 $T_2$를 쓰고, 각 테이블이 자기 해시 함수 $f_1(x)$와 $f_2(x)$를 갖는 방식이다. 값 $x$는 다음 순서로 삽입한다. 먼저 $T_1$의 $f_1(x)$번 칸에 $x$를 넣어 본다. 그 칸이 비어 있으면 거기에 $x$를 저장하고 끝난다. 비어 있지 않으면 충돌을 처리해야 한다. 그 칸에 들어 있던 값을 $y$라고 하자. $T_1$의 그 칸을 $x$로 덮어쓴 다음, 이번에는 $y$를 $T_2$의 $f_2(y)$번 칸에 넣어 본다. 여기서도 칸이 비어 있으면 $y$를 저장하고 끝난다. 비어 있지 않으면 그 칸에 있던 값 $z$를 $y$로 덮어쓰고, 다시 $z$를 $T_1$의 $f_1(z)$번 칸에 넣어 본다. 이렇게 빈 칸을 찾을 때까지 두 테이블을 오간다. 실제 구현이라면 교체 횟수가 일정 수를 넘었을 때 두 테이블을 재해싱하지만, 이 문제에서는 그런 일이 일어나지 않는다. 즉 삽입할 때마다 빈 칸을 반드시 찾는다.

두 테이블의 크기와 삽입할 값이 순서대로 주어질 때, 각 테이블의 최종 상태를 구하여라.

쿠쿠 해싱이라는 이름은 뻐꾸기의 습성에서 왔다. 뻐꾸기는 다른 새의 둥지에 자기 알을 낳고, 먼저 부화한 덩치 큰 뻐꾸기 새끼는 나머지 새끼를 둥지 밖으로 밀어내 먹이를 독차지한다. 잔인하지만 효율적이다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 양의 정수 세 개 $n_1$, $n_2$, $m$으로 시작한다. $n_1$과 $n_2$는 각각 테이블 $T_1$과 $T_2$의 크기이고, $m$은 삽입 횟수다. 그 뒤에 삽입할 정수 $m$개가 삽입 순서대로 주어지며, 모두 음이 아닌 정수다. 두 테이블은 처음에 비어 있고, 테이블 $T_i$는 해시 함수 $f_i(x) = x \bmod n_i$를 쓴다. 0이 세 개 있는 줄이 나오면 입력이 끝나며, 이 줄은 테스트 케이스가 아니다.

제한: $1 \le n_1, n_2 \le 1000$, $n_1 \ne n_2$

각 테스트 케이스마다 먼저 Case k:를 한 줄에 출력한다. $k$는 1부터 시작해 테스트 케이스마다 1씩 커지는 번호다. 그다음 $T_1$에 값이 하나라도 있으면 Table 1을 한 줄에 출력하고, 이어서 비어 있지 않은 칸을 인덱스가 작은 것부터 한 줄에 하나씩 i:v 형식으로 출력한다. $i$는 칸의 인덱스, $v$는 그 칸에 저장된 값이다. $T_2$도 같은 방식으로 Table 2와 칸 목록을 이어서 출력한다. 어느 테이블이 비어 있으면 그 테이블은 머리글을 포함해 아무것도 출력하지 않는다.