Зозуля для хешування
Хеш-таблиця цілих чисел — це структура даних, яка дозволяє виконувати операції вставки, видалення та пошуку цілих чисел за постійний час. Зазвичай, хеш-таблиця складається з масиву певного розміру n та хеш-функції f(x), яка часто визначається як f(x) = x mod n. Щоб вставити значення x у таблицю, обчислюють його хеш-значення f(x), яке використовується як індекс у хеш-таблиці для зберігання x. Наприклад, якщо x = 1234 і розмір хеш-таблиці 101, то 1234 буде збережено на позиції 22 = 1234 mod 101. Можливо, що на позиції 22 вже зберігається інше значення (наприклад, x = 22), що призводить до колізії. Колізії можуть бути вирішені різними методами, які ви можете обговорити зі своїм науковим керівником по дорозі додому з конкурсу.
Кукушка-хешування — це метод хешування, який використовує дві хеш-таблиці T_1 та T_2, кожна з яких має свою хеш-функцію f_1(x) та f_2(x). Вставка значення x відбувається так: спочатку намагаються зберегти x у T_1 за допомогою f_1(x). Якщо це місце порожнє, x просто зберігається там, і процес завершено. Інакше виникає колізія, яку потрібно вирішити. Нехай y — це значення, яке вже знаходиться в цьому місці. Ви замінюєте y на x у T_1, а потім намагаєтеся зберегти y у T_2 за допомогою f_2(y). Якщо це місце порожнє, ви зберігаєте y там, і процес завершено. Інакше замінюєте значення там (назвемо його z) на y, і тепер намагаєтеся зберегти z назад у T_1 за допомогою f_1(z), і так далі. Це продовжується, переміщуючись між двома таблицями, поки не знайдеться порожнє місце або не відбудеться певна кількість замін, після чого обидві таблиці перехешуються (це також можна обговорити зі своїм науковим керівником). Для цієї задачі, це останнє ніколи не станеться, тобто процес завжди триватиме, поки не буде знайдено порожнє місце, що гарантовано для кожного вставленого значення.
Зважаючи на розмір двох таблиць та серію вставок, ваше завдання — визначити, що зберігається в кожній з таблиць.
(Для тих, кого це цікавить, кукушка-хешування отримало свою назву від поведінки птаха кукушки, який відомий тим, що відкладає свої яйця в гнізда інших птахів разом з вже наявними яйцями. Коли більший пташеня кукушки вилуплюється, воно виштовхує інших пташенят з гнізда, таким чином отримуючи всю їжу для себе. Жахливо, але ефективно.)
Вхідні дані
Вхідні дані для кожного тестового випадку починаються з 3 додатних цілих чисел n_1 n_2 m, де n_1 та n_2 — це розміри таблиць T_1 та T_{2 } (з n_1, n_2 ≤ 1000 та n_1 ≠ n_2), а m — це кількість вставок. Після цього йтимуть m цілих чисел, які є значеннями для вставки в таблиці. Усі ці значення будуть невід'ємними. Кожна таблиця спочатку порожня, і таблиця T_{i } використовує хеш-функцію f_i(x) = x mod n_i. Рядок, що містить 3 нулі, завершить введення.
Вихідні дані
Для кожного тестового випадку виведіть непорожні позиції в T_1, а потім непорожні позиції в T_2. Використовуйте один рядок для кожної такої позиції у формі i:v, де i — це індекс позиції в таблиці, а v — це значення, яке там зберігається. Виводьте значення в кожній таблиці від найнижчого індексу до найвищого. Якщо будь-яка таблиця порожня, нічого не виводьте для цієї таблиці.