Hilbert çeşidləməsi
Elementlərin verilənlər bazasında rəqəmli açara uyğun yerləşdirilməsi nəinki müəyyən elementin axtarılmasını sadələşdirir, həmçinin mərkəzi prosessorun keş yaddaşını daha yaxşı istifadə etməyə imkan verir: yaddaşa yaxın istənilən verilənlər seqmenti oxşar acarlı elementləri təsvir edəcək. Bu məsələn, açarları müəyyən diapazonda olan bütün elementlərə müraciət etmək istədiyimiz zaman faydalıdır. Əgər açarlar GPS-naviqasiya sistemində yer alan 2D-torunun nöqtələri olarsa, bu daha da çətinləşir. Əgər (x, y) nöqtələri əvvəlcə x-ə, sonra isə y-ə görə çeşidlənərsə, onda yaddaşa yaxın olan nöqtələr eyni x koordinatlarında olacaqlar, lakin y koordinatları eyni olmaya bilər. y koordinatlı nöqtələr torda bir-birindən uzaqda olacaqlar. Məsafənin daha da saxlanması üçün biz verilənləri fəzanı dolduran kəsilməz əyri üzrə çeşidləyəcəyik.
Hilbert əyrisi adlanan fəzanın doldurulması əyrilərindən birinə baxaq. Hilbert əyrisi (0, 0) koordinatından başlayır və (S, 0)-da tamamlanır, dolaşma prosesində (0, 0) və (S, S) tinləri olan kvadratdan keçir. O növbəti rekursiv konstruksiyaya malikdir: kvadratı umumi (S / 2, S / 2) nöqtəsi olan dörd hissəyə ayıraq və onlardan hər birini tam Hilbert əyrisi ilə düzgün çevrilmiş və çoxsaylı nüsxə ilə dolduraq. Əvvəlcə aşağı sol kvadrat (0, 0)-dan (0, S / 2)-yə qədər gedən əyri ilə doldurulur. Sonra yuxarı sol kvadrat (0, S / 2)-dən (S / 2, S / 2)-yə qədər doldurulur. Sonra yuxarı sağ kvadrat (S / 2, S / 2)-dən (S, S / 2)-yə qədər doldurulur. Və nəhayət, aşağı sağ kvadrat (S, S / 2)-dən (S, 0)-a qədər doldurulur. Digər tərəfdən Hilbert əyrisi əyrilər ardıcıllığının riyazi limiti kimi qurula bilər ki, bunlardan ilk altısı şəkildə verilmişdir.
Sizdən verilmiş yerləri Hilbert əyrisindən keçməyə uyğun çeşidləmək tələb olunur. Qeyd edək ki, əyri özü ilə, məsələn, (S / 2, S / 2) nöqtəsində sonsuz sayda kəsişdiyi üçün, S-in tək kimi elan edilməsi bütün tam nöqtələrdən yalnız bir dəfə keçildiyinə bizə zəmanət verir.
Giriş verilənləri
İlk sətir iki n və S (1 ≤ n ≤ 200000, 1 ≤ S < 10^9, S təkdir) tam ədədlərini ehtiva edir. Sonra n sətir verilir. i + 1 sətri i-ci yeri x[i] və y[i] (0 ≤ x[i], y[i] ≤ S) iki tam koordinatlarla və 46 simvoldan - hərf və rəqəm (A - Z, a - z, 0 - 9) çox olmayan adı təsvir edir. Heç bir iki yer eyni koordinatlara və ya eyni ada malik deyil.
Çıxış verilənləri
n sətir - Hilbert əyrisi ilə keçilmiş ardıcıllıqda hər biri ayrı sətirdə yerlərin adlarını çeşidlənmiş şəkildə verin.