Pick

Ο Mirko διάβασε πρόσφατα για το θεώρημα του Pick που λέει τα εξής: στο σύστημα συντεταγμένων, αν σχεδιάσουμε ένα πολύγωνο του οποίου οι κορυφές είναι σημεία με ακέραιες συντεταγμένες και αν το ~A~ δηλώνει τo εμβαδον του, ~i~ ο αριθμός των σημείων με ακέραιες συντεταγμένες που βρίσκονται μέσα στο πολύγωνο και ~b~ ο αριθμός των σημείων με ακέραιες συντεταγμένες που βρίσκονται στις άκρες του (συμπεριλαμβανομένων των κορυφών του πολυγώνου), τότε ισχύει πάντα:

~A=i+\frac{b}{2}-1~.

Για να δοκιμάσει το θεώρημα, ο Mirko χρησιμοποίησε τον έξυπνο πίνακα του για να δημιουργήσει ένα πολύγωνο από μαγνητικά ραβδιά που, κατά τη διάρκεια της νύχτας, έπεσαν στο κάτω μέρος της του πίνακα λόγω της βαρύτητας. Τώρα, ο Mirko θέλει να κατασκεύασει ένα πολύγωνο ελάχιστου δυνατου εμβαδού χρησιμοποιώντας όλα τα ραβδιά που βρήκε. Ο Mirko μπορεί να μετακινήσει τα ραβδιά οπουδήποτε στον πίνακά του, αλλά δεν πρέπει να τα περιστρέψει. Ο Mirko είναι εξοπλισμένος με τα εξής:

• ~a~ οριζόντια ραβδιά μήκους ~1~,
  
• ~b~ κατακόρυφα ραβδιά μήκους ~1~,
  
• ~c~ διαγώνια ραβδιά μήκους ~\sqrt{2}~ που σχηματίζουν γωνία ~45\circ~ με το θετικό τμήμα του άξονα ~x~,
  
• ~d~ διαγώνιες ράβδους μήκους ~\sqrt{2}~ που σχηματίζουν γωνία ~135\circ~ με το θετικό τμήμα του άξονα ~x~.

Για το πολύγωνο από πάνω: ~A = 8~, ~i = 4~, ~b = 10.~      Τα ραβδιά με τα οποία ο Mirko είναι εξοπλισμένος.

Προσδιορίστε το πολύγωνο ελάχιστου δυνατού εμβαδού που μπορεί να ληφθεί έτσι ώστε να χρησιμοποιηθούν όλα τα ραβδιά. Μπορείτε να υποθέσετε ότι τα δεδομένα εισόδου είναι τέτοια ώστε να είναι δυνατή η κατασκευή τουλάχιστον ενός τέτοιου πολυγώνου.
Επίσης, είναι δυνατό να κερδίσετε μερικούς πόντους εάν, χρησιμοποιώντας όλα τα δοσμένα ραβδιά, κατασκευάσετε ένα έγκυρο πολύγωνο (αυτό δεν είναι απαραίτητα του ελάχιστου δυνατού εμβαδού). Για περισσότερες λεπτομέρειες, συμβουλευτείτε την ενότητα "Βαθμολογία".

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τέσσερις ακέραιους αριθμούς ~a~, ~b~, ~c~, ~d~ από την εργασία.

Έξοδος

Πρέπει να εκτυπώσετε ~n~ γραμμές όπου ~n = a + b + c + d~. Στη γραμμή ~j~, εκυπώστε τους ακέραιους αριθμούς ~x_j~ και ~y_j~ - τις συντεταγμένες της ~j~-οστής κορυφής του πολυγώνου. Η πρώτη κορυφή του πολυγώνου πρέπει να είναι ~(0, 0)~ και οι άλλες κορυφές μπορούν να εκτυπωθούν σε αυθαίρετη κατεύθυνση (είτε θετική είτε αρνητική). Επιτρέπεται ότι η διαδοχικές πλευρές του πολυγώνου να είναι παράλληλες, αλλά το πολύγωνο δεν μπορεί να αγγίξει ή να τέμνει τον εαυτό του.

Βαθμολογία

Σε όλα τα υποπροβλήματα, ισχύει ~0 \le a, b, c, d \le 100 ~και ~a + b + c + d \ge 3~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	5	~c = d = 0~
2	5	~a = b = 0~
3	10	~a + b + c + d \le 6~
4	10	~a + b + c + d \le 20~
5	10	~a + b + c + d \le 40~
6	10	~a + b + c + d \le 80~
7	10	~a + b + c + d \le 150~
8	10	~a + b + c + d \le 200~
9	10	~a + b + c + d \le 300~
10	20	Κανένας επιπλέον περιορισμός

Εάν, για ένα αρχείου ελέγχου, η λύση σας δεν παράγει ένα έγκυρο πολύγωνο που αποτελείται από τα δεδομένα ραβδιά, τότε βαθμολογείται ~0~ βαθμούς για το αντίστοιχο υποπρόβλημα. Εάν η λύση βγάζει ένα έγκυρο πολύγωνο που δεν είναι του ελάχιστου δυνατού εμβαδού, τότε μπορεί να κερδίσει μερικούς πόντους σύμφωνα με τους ακόλουθους κανόνες.
Για τo αρχείο ελέγχου ~j~, έστω ότι με ~r_j~ συμβολίζουμε τον λόγο του εμβαδού του ληφθέντος πολυγώνου και του ελάχιστου δυνατού πολυγώνου σε εμβαδό. Για το υποπρόβλημα ~k~, ας συμβολίσουμε με ~z_k~ τον μεγαλύτερο από τους αριθμούς ~r_j~, όπου ~j~ είναι το αρχείο ελέγχου από το αρχείο ελέγχου από το υποπρόβλημα ~k~. Το ποσοστό των πόντων ~P_k~ που βαθμολογείται η λύση για τo υποπρόβλημα ~k~ εξαρτάται από τον αριθμό ~z_k~ με τον ακόλουθο τρόπο: ~P_k = 10~ εάν ~z_k \ge 3~, και διαφορετικά υπολογίζεται ως:

~P_k = \frac{25}{8}(3-z_k)^4+10~

Επομένως, μια λύση που δεν είναι βέλτιστη μπορεί να συγκεντρώσει πόντους μεταξύ ~10~% και ~60~% για ένα συγκεκριμένο υποπρόβλημα, ανάλογα με τον λόγο του εμβαδού του ληφθέντος πολυγώνου και του βέλτιστου.

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

input

1 1 1 0

output

0 0 
1 1
0 1

input

0 0 6 4

output

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