Solar Flight

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

Λαμβάνουμε υπόψη ένα σύνολο ~N~ διαδρομών πτήσης, που όλες ταξιδεύουν ανατολικά από τη μια πόλη στην άλλη. Ένα αεροπλάνο μπορεί να θεωρηθεί ως ένα σημείο. Ο ουρανός από τον οποίο περνούν μπορεί να διαμορφωθεί ως καρτεσιανό επίπεδο, με συντεταγμένες ~x~ που αντιπροσωπεύουν την απόσταση ανατολικά από ένα αυθαίρετο σταθερό σημείο και τις συντεταγμένες ~y~ που αντιπροσωπεύουν το ύψος. Μας ενδιαφέρει μόνο το τμήμα του ουρανού με συντεταγμένες ~x~ στο κλειστό διάστημα [~0~, ~X~] (~1 \le X \le 10^9~), στο οποίο όλα τα μονοπάτια πτήσης είναι ευθείες γραμμές. Το ~i~-οστο αεροπλάνο πετά από το (~0, A_i~) στο (~X, B_i~) (~1 \le A_i, B_i \le 10^9~). Ολες οι τιμές ~A~ είναι διακριτές, όπως και όλες οι τιμές ~B~. Τα αεροπλάνα ταξιδεύουν με άγνωστες, πιθανώς μη σταθερές ταχύτητες κατά μήκος των μονοπατιών πτήσης τους, επομένως ανά πάσα στιγμή, ένα αεροπλάνο μπορεί να βρίσκεται οπουδήποτε κατά μήκος της διαδρομής του. Ωστόσο, είναι γνωστό ότι τα αεροπλάνα δεν θα συγκρουστούν ποτέ το ένα με το άλλο, οπότε αν δύο διαδρομές πτήσης διασταυρωθούν, και τα δύο αεροπλάνα δεν θα φτάσουν στο σημείο διασταύρωσης ακριβώς την ίδια στιγμή.

Τα αεροπλάνα έχουν επίσης έναν παράγοντα παρεμβολής: κάθε αεροπλάνο ~i~ έχει έναν παράγοντα παρεμβολής ~C_i~ (~1 \le C_i \le 10^9~), ο οποίος είναι ένα μέτρο του πόσο το αεροπλάνο ~i~ θα επηρέαζε αρνητικά την ικανότητα απορρόφησης του ήλιου οποιουδήποτε αεροπλάνου κάτω από αυτό.

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

Δεδομένων αυτών των πληροφοριών, καθώς και μιας σταθερής απόστασης ~K~ (~1 \le K \le X~), πρέπει να απαντήσετε σε ~Q~ ερωτήματα σχετικά με τις πιθανές επιπτώσεις στα ηλιακά πάνελ των αεροπλάνων σε διάφορες χρονικές στιγμές. Το ~i~-οστο ερώτημα ζητά τη μεγαλύτερη πιθανή ποσότητα κατά την οποία τα ηλιακά πάνελ του αεροπλάνου ~P_i~ θα μπορούσαν να παρεμποδιστούν σε μία μόνο χρονική στιγμή, σε οποιοδήποτε σημείο ενώ η συντεταγμένη ~x~ του αεροπλάνου ανήκει στο κλειστό διάστημα [~S_i, S_i + K~] (~0 \le S_i \le X - K~).

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις, χωρισμένους με κενό, ακέραιους: ~X~ (~1 \le X \le 10^9~), τη μέγιστη συντεταγμένη ~x~, ~K~ (~1 \le K \le X~), τη σταθερά απόστασης, ~N~ (~1 \le N \le 2\,000~), τον αριθμό των διαδρομών πτήσης, ~Q~ (~1 \le Q \le 800\,000~), τον αριθμό των ερωτήσεων.

Καθεμία από τις επόμενες ~N~ γραμμές περιέχει τρεις ακέραιους, ~A_i~, ~B_i~ και ~C_i~, για ~i = 1 ... N~ (~1 \le A_i, B_i, C_i \le 10^9~), που αντιπροσωπεύουν το αεροπλάνο ~i~, την αρχική συντεταγμένη ~y~, την τελική συντεταγμένη ~y~ και τον παράγοντα παρεμβολής (αντίστοιχα).

Καθεμία από τις επόμενες ~Q~ γραμμές περιέχει δύο ακέραιους ~P_i~ και ~S_i~, για ~i = 1 ... Q~ που αντιπροσωπεύουν την ερώτηση που αφορά το αεροπλάνο ~P_i~ όσο η συντεταγμένη του ~x~ ανήκει στο διάστημα [~S_i, S_i + K~].

Βαθμολογία

Για το 40% της βαθμολογίας, ~Q \le 1\,000~.

Έξοδος

Η έξοδος αποτελείται από ~Q~ γραμμές, καθεμία με την ακέραια απάντηση στην ~i~-οστη ερώτηση, για ~i = 1 ... Q~.

Παράδειγμα

input

12 4 3 3
1 4 5
2 2 3
6 3 6
2 1
1 8
3 0

output

11
6
0

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

Παρακάτω είναι ένα διάγραμμα των διαδρομών πτήσης των αεροπλάνων:

Η πρώτη ερώτηση είναι για το αεροπλάνο ~2~ για συντεταγμένες ~x~ στο κλειστό διάστημα [~1, 5~]. Όσο το αεροπλάνο είναι σε μία συντεταγμένη ~x~ μικρότερη ή ίση του ~4~, μπορεί να καλυφθεί από το αεροπλάνο ~3~, αλλά σίγουρα όχι από το αεροπλάνο ~1~. Ωστόσο, όταν είναι σε μία συντεταγμένη ~x~ μεγαλύτερη του ~4~, μπορεί να καλυφθεί και από τα δύο αεροπλάνα. Οπότε, η απάντηση σε αυτή την ερώτηση είναι το άθροισμα των παραγόντων παρεμβολής των άλλων αεροπλάνων, ~5 + 6 = 11~.

Για τη δεύτερη ερώτηση, το αεροπλάνο ~1~ θα μπορούσε να καλυφθεί από το αεροπλάνο ~3~ όσο έχει συντεταγμένη ~x~ μικρότερη του ~10~ και δεν θα καλύπτεται από τίποτα όσο έχει συντεταγμένη ~x~ μεγαλύτερη ή ίση του ~10~. Οπότε, είναι πιθανό να το παρεμβάλει το αεροπλάνο ~3~ με παράγοντα παρεμβολής ~6~.

Ούτε το αεροπλάνο ~1~ ούτε το αεροπλάνο ~2~ μπορούν να είναι ακριβώς πάνω από το αεροπλάνο ~3~ μέχρι να φτάσει συντεταγμένη ~x~ ~10~, οπότε η απάντηση στην τελευταία ερώτηση είναι ~0~.