Hashing üçün Dəli
Tam ədədli hash cədvəli, tam ədədlərin sabit zamanda əlavə edilməsi, silinməsi və axtarışını dəstəkləyən bir məlumat strukturdur. Ənənəvi hash strukturları müəyyən ölçüdə bir massivdən (hash cədvəli) və adətən f(x) = x mod n olan bir hash funksiyası f(x)-dən ibarətdir. Bir x dəyərini cədvələ əlavə etmək üçün onun hash dəyərini f(x) hesablayırsınız ki, bu da x-i saxlamaq üçün hash cədvəlindəki indeks kimi xidmət edir. Məsələn, əgər x = 1234 və hash cədvəli 101 ölçüsündədirsə, onda 1234 22 = 1234 mod 101 yerində saxlanılacaq. Təbii ki, 22 yerində artıq başqa bir dəyər (x = 22 məsələn) saxlanıla bilər ki, bu da toqquşmaya səbəb olur. Toqquşmalar müxtəlif yollarla həll edilə bilər ki, bunları müsabiqədən evə gedərkən müəllim məsləhətçinizlə müzakirə edə bilərsiniz.
Kuku hashing, hər biri öz hash funksiyasına f_1(x) və f_2(x) malik olan iki hash cədvəli T_1 və T_2 istifadə edən bir hashing formasıdır. Bir x dəyərinin əlavə edilməsi belə həyata keçirilir: əvvəlcə T_1-də f_1(x) istifadə edərək x-i saxlamağa çalışırsınız. Əgər bu yer boşdursa, sadəcə x-i orada saxlayırsınız və işiniz bitir. Əks halda, həll edilməli olan bir toqquşma var. y həmin yerdə hazırda olan dəyər olsun. T_1-də y-ni x ilə əvəz edirsiniz və sonra T_2-də f_2(y) istifadə edərək y-ni saxlamağa çalışırsınız. Yenə də, əgər bu yer boşdursa, y-ni orada saxlayırsınız və işiniz bitir. Əks halda, oradakı dəyəri (ona z deyək) y ilə əvəz edirsiniz və indi z-i T_1-də f_1(z) istifadə edərək saxlamağa çalışırsınız və s. Bu, iki cədvəl arasında irəli-geri davam edir, ya boş bir yer tapılana qədər, ya da müəyyən sayda dəyişiklik baş verənə qədər, bu zaman hər iki cədvəli yenidən hash edirsiniz (yenə də, müəllim məsləhətçinizlə müzakirə edəcəyiniz bir şey). Bu problemin məqsədləri üçün, bu sonuncu hal heç vaxt baş verməyəcək, yəni proses hər əlavə edilmiş dəyər üçün boş bir yer tapılana qədər davam etməlidir ki, bu da təmin ediləcəkdir.
İki cədvəlin ölçüsü və bir sıra əlavələr verildikdə, sizin işiniz hər bir cədvəldə saxlanılanları müəyyən etməkdir.
(Maraqlananlar üçün, kuku hashing adını kuku quşunun davranışından alır, hansı ki, digər quşların yuvalarına uçaraq öz yumurtalarını orada olan yumurtalarla birlikdə qoyur. Daha böyük kuku balası çıxanda, digər balaları yuvadan çıxarır və beləliklə bütün qidanı özü üçün alır. Qorxunc, amma səmərəli.)
Giriş verilənləri
Hər test halı üçün giriş 3 müsbət tam ədəd n_1 n_2 m ilə başlayır, burada n_1 və n_2 T_1 və T_{2 } cədvəllərinin ölçüləridir (n_1, n_2 ≤ 1000 və n_1 ≠ n_2) və m əlavə etmələrin sayıdır. Bundan sonra cədvəllərə əlavə ediləcək m tam ədəd dəyərlər gəlir. Bu dəyərlərin hamısı qeyri-mənfi olacaq. Hər cədvəl əvvəlcə boşdur və T_{i } cədvəli f_i(x) = x mod n_i hash funksiyasından istifadə edir. 3 sıfırdan ibarət bir sətir girişi tamamlayacaq.
Çıxış verilənləri
Hər test halı üçün, əvvəlcə T_1-dəki boş olmayan yerləri, sonra isə T_2-dəki boş olmayan yerləri çıxış edin. Hər belə yer üçün bir sətir istifadə edin və i:v formasında yazın, burada i cədvəlin indeks yeridir və v orada saxlanılan dəyərdir. Hər cədvəldəki dəyərləri ən aşağı indeksdən ən yüksək indeksə qədər çıxış edin. Əgər hər hansı bir cədvəl boşdursa, həmin cədvəl üçün heç nə çıxış etməyin.