Gates

Βρίσκεστε σε ένα διάδρομο αεροδρομίου με ~G~ (~1 \le G \le 10^9~) πύλες, αριθμημένες από ~1~ έως ~G~ με τη σειρά. Η είσοδος στην πύλη ~i~ απέχει ~100 \cdot i~ μέτρα από την αρχή του διαδρόμου.

Υπάρχουν επίσης ~N~ (~0 \le N \le 10^5~) κινούμενοι διάδρομοι. Ο ~i~-οστος κινούμενος διάδρομος πηγαίνει από την είσοδο στην πύλη ~A_i~ (~1 \le A_i \le G~) στην είσοδο σε μια διαφορετική πύλη ~B_i~ (~1 \le B_i \le G~) με ταχύτητα ~S_i~ (~1 \le S_i \le 10^9~) μέτρα ανά λεπτό, μόνο προς μία κατεύθυνση. Σε κάθε σημείο κατά μήκος του διαδρόμου, υπάρχει το πολύ ένας κινούμενος διάδρομος που κινείται προς κάθε κατεύθυνση (προς την αρχή του διαδρόμου ή μακριά από αυτή). Ωστόσο, είναι πιθανό ότι ένας κινούμενος διάδρομος ξεκινά από την ίδια πύλη που ένας άλλος κινούμενος διάδρομος, κινούμενος προς την ίδια κατεύθυνση, τελειώνει.

Μπορείτε να περπατήσετε προς οποιαδήποτε κατεύθυνση κατά μήκος του διαδρόμου με ταχύτητα ~W~ (~1 \le W \le 10^9~) μέτρα ανά λεπτό. Επιπλέον, όταν βρίσκεστε στην αρχή ενός κινούμενου διαδρόμου, μπορείτε να επιλέξετε να τον χρησιμοποιήσετε, οπότε Θα σας μεταφέρει απευθείας στο τέλος του - δεν μπορείτε να ανέβετε ή να κατέβετε μεταξύ αυτών των σημείων. Ενώ είστε στον κινούμενο διάδρομο ~i~, θα μετακινείστε με ταχύτητα ~W + S_i~ μέτρα ανά λεπτό.

Για να διασκεδάσετε τον εαυτό σας ενώ περιμένετε την πτήση σας (η οποία, φυσικά, έχει καθυστερήσει), έχετε θέσει ~Q~ (~1 \le Q \le 10^5~) ερωτήματα στον εαυτό σας. Το ~i~-οστο ερώτημα περιλαμβάνει την εξεύρεση του ελάχιστου χρόνου στον οποίο μπορείτε να πάτε από την πύλη ~X_i~ (~1 \le X_i \le G~) στην πύλη ~Y_i~ (~1 \le Y_i \le G~). Για να κάνουμε τα πράγματα πιο ενδιαφέροντα, έχετε αποφασίσει ότι δεν θα επιβιβαστείτε στην πτήση σας, εκτός αν μπορείτε να απαντήσετε σωστά σε όλα αυτά τα ερωτήματα - γι 'αυτό καλύτερα να μην τα κάνετε θάλασσα!

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις ακέραιους: ~G~ (~1 \le G \le 10^9~), τον αριθμός από τις πύλες, ~W~ (~1 \le W \le 10^9~), την ταχύτητα βαδίσματος, ~N~ (~0 \le N \le 10^5~), τον αριθμό των κινούμενων διαδρόμων και ~Q~ (~1 \le Q \le 10^5~), τον αριθμό των ερωτημάτων.

Οι επόμενες ~N~ γραμμές καθεμία περιέχουν τρεις ακέραιους που έχουν να κάνουν με τον κινούμενο διάδρομο ~i~ (~i = 1 ... N~): ~A_i~ (~1 \le A_i \le G~), την αρχική πύλη, ~B_i~ (~1 \le B_i \le G~), την τελική πύλη, ~S_i~ (~1 \le S_i \le 10^9~), την ταχύτητα. Σημειώστε ότι ~A_i \ne B_i~ για κάθε ~i~.

Οι επόμενες ~Q~ γραμμές καθεμία περιέχουν δύο ακέραιους που έχουν να κάνουν με το ερώτημα ~i = 1 ... Q~: ~X_i~ (~1 \le X_i \le G~), την αρχική πύλη και ~Y_i~ (~1 \le Y_i \le G~), την τελική πύλη.

Μπορείτε να υποθέσετε ότι για ορισμένες περιπτώσεις ελέγχου, τουλάχιστον κάποια από τα ~G~, ~N~ και ~Q~ είναι μικρά. Αυτή η πληροφορία μπορεί να είναι χρήσιμη, μπορεί και όχι.

Έξοδος

Η έξοδος είναι ~Q~ γραμμές, με κάθε γραμμή να περιέχει έναν πραγματικό αριθμό που είναι ο ελάχιστος χρόνος που απαιτείται για να πάμε από την πύλη ~X_i~ στην πύλη ~Y_i~ (σε λεπτά), για ~i = 1 ... Q~. Η έξοδος θα κριθεί ως σωστή αν η εκτυπωμένη απάντηση είναι εντός ενός παράγοντα ~10^{-4}~ από τη σωστή λύση: δηλαδή, αν το ~D~ είναι η σωστή απάντηση, οι τιμές στο διάστημα [~D \cdot (1 - 10^{-4})~, ~D \cdot (1 + 10^{-4})~] θα κριθεί ως σωστή.

Παράδειγμα

input

6 10 3 4
2 3 15
4 2 150
3 6 290
3 2
2 3
1 4
4 6

output

10.0
4.0
24.0
6.25

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

Για το πρώτο ερώτημα, θα πρέπει απλά να περπατήσετε από την πύλη ~3~ στην πύλη ~2~, διανύοντας ~100~ μέτρα με μία ταχύτητα ~10~ μέτρα ανά λεπτό.

Για το δεύτερο ερώτημα, θα πρέπει να ανεβείτε αμέσως στον κινούμενο διάδρομο πηγαίνοντας απο την πύλη ~2~ στην πύλη ~3~, διανύοντας ~100~ μέτρα με μία ταχύτητα ~10 + 15 = 25~ μέτρα ανά λεπτό.

Για το τρίτο ερώτημα, θα πρέπει να περπατήσετε μέχρι την πύλη ~2~ (θα σας πάρει ~10~ λεπτά), μετά να πάρετε τον κινούμενο διάδρομο όπως πριν (θα σας πάρει ~4~ λεπτά), και μετά να περπατήσετε μέχρι την πύλη ~4~ (θα σας πάρει ~10~ λεπτά).

Τέλος, για το τέταρτο ερώτημα, θα πρέπει να πάρετε τον κινούμενο διάδρομο από την πύλη ~4~ στην πύλη ~2~ (θα σας πάρει 1.25 λεπτά), μετά τον κινούμενο διάδρομο από την πύλη ~2~ στην πύλη ~3~ (θα σας πάρει ~4~ λεπτά) και τέλος τον κινούμενο διάδρομο από την πύλη ~3~ στην πύλη ~6~ (θα σας πάρει ~1~ λεπτό).