A Game with Grundy

Ο Grundy παίζει το αγαπημένο του παιχνίδι - κρυφτό.

Οι ~N~ φίλοι του στέκονται σε τοποθεσίες στον άξονα ~x~ ενός δισδιάστατου επιπέδου - ο ~i~-οστος είναι στις συντεταγμένες (~x_i~, ~0~). Κάθε φίλος μπορεί να βλέπει σε μια τριγωνική "σφήνα" που εκτείνεται κάθετα προς τα πάνω από την θέση του - η τριγωνική "σφήνα" όρασης του ~i~-οστού φίλου θα προσδιορίζεται από δύο γραμμές: μία με κλίση ~v_i~ / ~h_i~ και η άλλη με κλίση -~v_i~ / ~h_i~. Ένας φίλος δεν μπορεί να δεί ένα σημείο που βρίσκεται ακριβώς πάνω σε μια από τις γραμμές αυτές.

Ο Grundy μπορεί να διαλέξει να κρυφτεί σε οποιαδήποτε τοποθεσία (~a~, ~Y~), όπου ~a~ είναι ένας ακέραιος που ικανοποιεί την ανίσωση ~L~ ~\le~ ~a~ ~\le~ ~R~, και ~L~, ~R~ και ~Y~ δίνονται ακέραιες σταθερές.

Κάθε πιθανή τοποθεσία μπορεί να είναι ορατή από καποιον από τους φίλους του Grundy (δηλαδή, αυστηρά εντός της τριγωνικής "σφήνας" όρασης του).

Ο Grundy θα ήθελε να ξέρει σε πόσα διαφορετικά σημεία μπορεί να σταθεί έτσι ώστε να είναι ορατός από το πολύ ~i~ φίλους του, για κάθε πιθανή τιμή του ~i~ από το ~0~ ως το ~N~.

Είσοδος

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

Η επόμενη γραμμή περιέχει τρεις ακέραιους: ~L~, ~R~ και ~Y~ (-~1\,000\,000\,000~ ~\le~ ~L~ ~\le~ ~R~ ~\le~ ~1\,000\,000\,000~, ~1~ ~\le~ ~Y~ ~\le~ ~1\,000\,000~).

Κάθε μια από τις επόμενες ~N~ γραμμές περιέχει τρεις ακέραιους: η ~i~-οστη τέτοια γραμμή περιέχει ~x_i~ (~L~ ~\le~ ~x_i~ ~\le~ ~R~), την τιμή ~x~ της θέσης του φίλου ~i~ ακολουθούμενη από δύο ακέραιους ~v_i~ και ~h_i~ (~1~ ~\le~ ~v_i~, ~h_i~ ~\le~ ~100~). Οι κλίσεις ~v_i~ / ~h_i~ και -~v_i~ / ~h_i~ ορίζουν την τριγωνική "σφήνα" όρασης του φίλου ~i~.

Βαθμολογία

Για ~15~ από τους ~25~ διαθέσιμους βαθμούς, -~1\,000\,000~ ~\le~ ~L~ ~\le~ ~R~ ~\le~ ~1\,000\,000~.

Έξοδος

Η έξοδος είναι ~N + 1~ γραμμές, όπου κάθε γραμμή ~i~ (~0~ ~\le~ ~i~ ~\le~ ~N~) περιέχει τον ακέραιο αριθμό θέσεων στις οποίες μπορεί να σταθεί ο Grundy και να είναι ορατός από το πολύ ~i~ φίλους του.

Παράδειγμα

input

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

output

5
12
15
15

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

Υπάρχουν τρεις φίλοι με τις ακόλουθες τριγωνικές "σφήνες" όρασης, μαζί με τις πιθανές θέσεις που μπορεί να τοποθετηθεί ο Grundy, όπως φαίνεται στο παρακάτω διάγραμμα:

Προσέξτε πως τα σημεία (~2~, ~3~) και (~4~, ~3~) είναι ορατά μόνο από τον φίλο στην θέση ~0~, καθώς βρίσκονται στα όρια της τριγωνικής "σφήνας" όρασης του φίλου στη θέση ~3~.