Graskrizja

Το Peatown έχει γίνει μητρόπολη. Μπορούμε να το παρατηρήσουμε ως ένα ορθογώνιο πλέγμα δρόμων. Υπάρχουν πενήντα χιλιάδες κάθετοι δρόμοι που εκτείνονται από βορρά-νότο (με ετικέτα συντεταγμένες ~x~ από 1 έως ~50\,000~) και πενήντα χιλιάδες οριζόντιους δρόμους που εκτείνονται από ανατολικά προς τα δυτικά (με ετικέτα συντεταγμένες y από 1 έως ~50\,000~). Όλοι οι δρόμοι είναι αμφίδρομοι. Η διασταύρωση μιας οριζόντιας και κάθετης οδού ονομάζεται διασταύρωση.
Οι κάτοικοι του Peatown είναι πολύ ανεύθυνοι και απερίσκεπτοι. Οδηγούν σαν ηλίθιοι, οπότε ο δήμαρχος του Peatown αποφάσισε να τοποθετήσει φανάρια σε ~N~ διασταυρώσεις. Ένα μονοπάτι ανάμεσα σε δύο διασταυρώσεις είναι επικίνδυνο αν υπάρχει στροφή χωρίς φανάρι. Διαφορετικά είναι ακίνδυνο.
Δεν είναι δυνατό να διασφαλιστεί ότι όλα τα μονοπάτια είναι ακίνδυνα, αλλά ο δήμαρχος του Peatown είναι ικανοποιημένος εάν ανάμεσα σε κάθε δύο φανάρια τουλάχιστον ένα από τα συντομότερα μονοπάτια είναι αβλαβές. Δυστυχώς, η τρέχουσα κατανομή των φωτεινών σηματοδοτών είναι πολύ επικίνδυνη. Το καθήκον σας είναι να τοποθετήσετε επιπλέον φανάρια (λιγότερα από ~700\,000~ από αυτά) έτσι ώστε το σύνολο των φωτεινών σηματοδοτών (που περιέχει και νέους και παλιούς φωτεινούς σηματοδότες) να ανταποκρίνεται στις απαιτήσεις του δημάρχου. Σίγουρα έχετε μυαλό, οπότε βοηθήστε τους κατοίκους του Peatown!

Είσοδος

Η πρώτη γραμμή εισόδου αποτελείται από έναν ακέραιο αριθμό ~N\;(2 \leq N \leq 50\,000)~, τον αριθμό των αρχικά τοποθετημένων φωτεινών σηματοδοτών.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μια θέση ενός φαναριού, που παριστάνεται με ακέραιους αριθμούς ~X~ και ~Y\;(1 \leq X,\;Y \leq 50\,000)~, συντεταγμένες των κάθετων και οριζόντιων οδών που τέμνονται σε αυτή τη διασταύρωση. Όλα τα φανάρια θα είναι μοναδικά.

Έξοδος

Τυπώστε τις θέσεις των νέων φαναριών, το καθένα στη δική του γραμμή.
Επιτρέπεται η τοποθέτηση πολλαπλών φωτεινών σηματοδοτών στην ίδια τοποθεσία.
Ο αριθμός των νέων φωτεινών σηματοδοτών πρέπει να είναι μικρότερος από 700 000.

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

input

2
1 1
3 3

output

1 3

input

3
2 5
5 2
3 3

output

3 5
5 3

input

5
1 3
2 5
3 4
4 1
5 2

output

1 5
3 3
3 5
4 2
4 3