Artur

Σίγουρα έχετε ακούσει τον θρύλο του Βασιλιά Αρθούρου και των Ιπποτών της Στρογγυλής Τραπέζης. Σχεδόν όλες οι εκδοχές αυτής της ιστορίας επισημαίνουν περήφανα ότι η στρογγυλότητα του Στρογγυλού Τραπεζιού σχετίζεται στενά με την πίστη του Άρθουρου για ισότητα μεταξύ των Ιπποτών. Αυτό είναι ψέμα! Στην πραγματικότητα, η επιλογή του τραπεζιού του Αρθούρου εξαρτάται από τα παιδικά του τραύματα.

Στην πραγματικότητα, ο Άρθουρος αναγκάστηκε να καθαρίζει τετραγωνικά τραπέζια από νεαρή ηλικία, αφού παιζόταν σε αυτά ένα τουρνουά ράβδοι pick-up¹. Μετά το τουρνουά, συνήθως θα υπήρχαν ένα σωρό ράβδοι στο τραπέζι που δεν αγγίζουν το ένα το άλλο. Στο πνεύμα του παιχνιδιού, οι διοργανωτές εξέδωσαν αυστηρούς κανονισμούς για τις τραπεζοκαθαριστές. Πιο συγκεκριμένα, οι ράβδοι στο τραπέζι πρέπει να αφαιρούνται ένα-ένα με τρόπο ώστε οι καθαριστές να τα τραβούν με τον συντομότερο τρόπο προς την άκρη του τραπεζιού που βρίσκεται πιο κοντά στο σημείο που κάθονται αυτήν τη στιγμή. Επίσης, δεν πρέπει να περιστρέφουν ή να αγγίζουν τα άλλα μπαστούνια ενώ το κάνουν αυτό (ούτε καν στα άκρα).

Σε αυτήν την εργασία, θα αναπαραστήσουμε τον πίνακα στο σύστημα συντεταγμένων με ένα τετράγωνο που έχει αντίθετα σημεία στις συντεταγμένες ~(0,\;0)~ και ~(10\;000,\;10\;000)~, ενώ οι ράβδοι θα αναπαρασταθούν με ευθύγραμμα τμήματα που βρίσκονται εντός εκείνο το τετράγωνο. Θα υποθέσουμε ότι ο Αρθούρος κάθεται στην άκρη του τραπεζιού ξαπλωμένος στον άξονα ~x~. Στη συνέχεια, η κίνηση του ραβδιού καταλήγει στη μετάφραση του τμήματος γραμμής κατά μήκος της συντομότερης διαδρομής προς τον άξονα ~x~ έως ότου το ραβδί πέσει από το τραπέζι (όπως φαίνεται στην εικόνα). Είναι καθήκον σας να βοηθήσετε τον Άρθουρο να καθορίσει τη σειρά των κινήσεων του ραβδιού που πληροί τις απαιτήσεις της προηγούμενης παραγράφου.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 5\,000)~, τον αριθμό των ραβδιών στον πίνακα. Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει τέσσερις ακέραιους ~x_1,\;y_1,\; x_2,\;y_2\;(0 \leq x_1, y_1, x_2, y_2 \leq 10\,000)~ που δηλώνουν τα σημεία ακμής ενός ραβδιού.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει ετικέτες ραβδιών που χωρίζονται με διάστημα, με τη σειρά που πρέπει να αφαιρεθούν από το τραπέζι. Η ετικέτα ενός ραβδιού αντιστοιχεί στη θέση του στην ακολουθία εισαγωγής.

Εάν υπάρχουν πολλαπλές πιθανές λύσεις, τυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 40% των συνολικών πόντων, θα έχει ~1 \leq N \leq 10~. Σε δοκιμαστικές περιπτώσεις αξίας ~60~%των συνολικών πόντων, θα έχει ~1 \leq N \leq 300~

Παραδείγματα

input

4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3

output

2 4 1 3

Επεξήγηση του 1ου παραδείγματος:

Το παράδειγμα αντιστοιχεί στην εικόνα από την εργασία. Μια άλλη πιθανή λύση είναι το ~2\;1\;4\;3~.

input

4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1

output

4 3 1 2

input

3
4 6 5 5
2 1 15 1
3 2 8 7

output

2 3 1

Ένα παιχνίδι που περιλαμβάνει προσεκτικά κινούμενα μπαστούνια.