Dronların məhv edilməsi
Ralf öz oyunundan qaçdıqdan sonra, onu tapmaq üçün n xüsusi təlim keçmiş dron göndərildi. Lakin, Ralf sadə biri deyil və əlində taret ilə müdafiə mövqeyi tutub.
Vəziyyəti diqqətlə qiymətləndirən Ralf başa düşdü ki, əgər o, koordinatların başlanğıc nöqtəsində - (0, 0) nöqtəsində yerləşən müstəvini nəzərdən keçirsə, onda i-ci dron (x[i], y[i]) koordinatlarında yerləşir. Lakin, Ralf vəziyyəti kəşf edərkən, dronlar onu gördülər, yəni hərəkətə keçmək vaxtıdır. Bir saniyə ərzində Ralf taret ilə istənilən dronu vura bilər, lakin sağ qalan dronlar bundan sonra üfüqi, şaquli və ya diaqonal üzrə onlara qonşu olan 8 nöqtədən istənilən birinə hərəkət edə bilərlər (bu zaman bəzi dronlar eyni koordinatlı nöqtələrdə ola bilərlər).
Dronların vəzifəsi Ralfa, yəni (0, 0) nöqtəsinə çatmaqdır, Ralfın vəzifəsi isə onların hamısını ona çatmadan vurmaqdır. Ralf sizə zəmanət verir ki, heç vaxt qaçırmayacaq və hər atışda məhz bir dronu vuracaq. Sizdən isə xahiş edir ki, ona dronları hansı ardıcıllıqla vuracağını deyəsiniz. Ona kömək edin — dronları hansı ardıcıllıqla vuracağını deyin ki, onlar (0, 0) nöqtəsinə çatmasınlar, ya da deyin ki, bunu etmək mümkün deyil və Ralfın qaçması daha yaxşıdır.
Giriş məlumatları
Birinci sətirdə dronların sayı n (1 ≤ n ≤ 10^5) verilir. Növbəti n sətirdə i-ci dronun koordinatları olan iki ədəd x[i] və y[i] verilir (|x[i]|, |y[i]| ≤ 10^5). Zəmanət verilir ki, (0, 0) nöqtəsində dron yoxdur.
Çıxış məlumatları
Bir sətirdə n ədəd 1-dən n-ə qədər - Ralfın dronlara hansı ardıcıllıqla atəş açmalı olduğunu göstərən dronların nömrələrini verin. Əgər hansısa dron hər halda (0, 0) nöqtəsinə çatacaqsa, -1 çıxarın. Əgər bir neçə həll mövcuddursa, onlardan istənilən birini çıxarın.