Pod starim krovovima

Σκηνικό: Το θρυλικό πανδοχείο του Ζάγκρεμπ που ονομάζεται Kod Žnidaršića.

Χρόνος: Το έτος 1936.

Σύνοψη της υπόθεσης: Ο Franjo και οι φίλοι του συζητούν τα τωρινά γεγονότα στην Αβησσυνία απολαμβάνοντας μερικά ποτά στο μπαρ. Ο γιος του, ο μικρός Perica, κάθεται σε ένα μικρό τραπέζι στη γωνία του μπαρ. Μπροστά στον Perica υπάρχουν ~N~ ποτήρια βολικά αριθμημένα από το ~1~ έως το ~N~. Ο όγκος (σε νανολίτρα) κάθε ποτηριού είναι επίσης γνωστός καθώς και η ποσότητα του υγρού που βρίσκεται αυτή τη στιγμή μέσα σε αυτό.

Πρόβλημα: Ο μικρός Perica θέλει να μάθει ποιος είναι ο μεγαλύτερος δυνατός αριθμός ποτηριών που μπορεί να αδειάσει ρίχνοντας το υγρό ανάμεσα στα ποτήρια. Μπορεί να ρίχνει ελεύθερα οποιονδήποτε ακέραιο αριθμό νανολίτρων από ένα ποτήρι σε ένα άλλο, όσες φορές θέλει, αρκεί να μην χυθεί υγρό.

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

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N~ ~(1 \le N \le 1\,000)~.

Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει δύο ακέραιους ~T_i~ ~(0 \le T_i \le 10^9)~ και ~Z_i~ ~(1 \le Z_i \le 10^9)~ οι οποίοι αντιπροσωπεύουν την τρέχουσα ποσότητα υγρού στο ~i~-οστό ποτήρι και τον όγκο του αντίστοιχα. Δίνονται και οι δύο ποσότητες σε νανολίτρα. Η τρέχουσα ποσότητα υγρού δεν μπορεί να είναι μεγαλύτερη από τον όγκο του γυαλιού, δηλαδή ~T_i \le Z_i~.

Έξοδος

Στην πρώτη γραμμή θα πρέπει να τυπώσετε τον μεγαλύτερο αριθμό ποτηριών που μπορούν να αδειάσουν ρίχνοντας το υγρό μέσα σε ποτήρια.

Στη δεύτερη γραμμή θα πρέπει να τυπώσετε την ποσότητα του υγρού σε κάθε ποτήρι αφού ο Perica εκτελέσει τις απραίτητες εκχύσεις. Τα ποτήρια πρέπει να είναι διατεταγμένα από το ~1~ έως το ~N~.

Βαθμολογία

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

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας ~20~ πόντων, όλα τα ποτήρια θα έχουν τον ίδιο όγκο.

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

input

5
2 6
1 6
0 6
6 6
5 6

output

2
6 6 2 0 0

input

5
4 5
2 7
5 5
0 10
7 9

output

3
0 0 0 10 8

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

Μία από τις πιθανές διαμορφώσεις έκχυσης είναι η εξής:

1. Ρίξτε τα πάντα από το ποτήρι ~1~ στο ποτήρι ~2~.

2. Ρίξτε τα πάντα από το ποτήρι ~2~ στο ποτήρι ~4~.

3. Ρίξτε 4 νανόλιτρα από το γυαλί ~3~ στο ποτήρι ~4~.

4. Ρίξτε 1 νανόλιτρο από το γυαλί ~3~ στο ποτήρι ~5~.

Τώρα τα ποτήρια νούμερο ~1~, ~2~ και ~3~ είναι άδεια.

input

8
2 6
3 4
1 1
9 10
0 10
4 5
6 8
3 9

output

5
0 0 0 9 10 0 0 9