Problem description

Ola uwielbia szybką jazdę po swoim mieście. Wie jednak, że czasem wiąże się to z nieprzyjemnością otrzymania mandatu od srogiego pana w niebieskiej czapce.

Ola nie przekracza prędkości o więcej niż limit określony dla danego odcinka drogi (inaczej zabraliby jej prawo jazdy, a na to nie może sobie pozwolić).

Jeżeli już się zostanie złapanym na szybkiej jeździe, to wysokość mandatu jest liczona proporcjonalnie do czasu o jaki szybciej przejechaliśmy dany odcinek (prowadzone są odcinkowe pomiary czasu przejazdu). Maksymalny mandat otrzymuje się przy przejechaniu w połowie czasu jaki by nam zajęła jazda zgodnie z przepisami prawa. Przykładowo, jeżeli nieprzekraczając limitu prędkości jesteśmy w stanie przejechać w czasie 200, a my przejechalismy go w czasie 140, to zapłacimy 60 maksymalnej kwoty mandatu.

Ola ma ograniczony budżet i jest w stanie pokryć koszt mandatów w wysokości maksymalnie K. Zastanawia się teraz, ile czasu zajmie jej przejechaniu między pewnymi skrzyżowaniami, tak aby nawet gdyby dostała mandat za każde przekroczenie prędkości, to nie zapłaciłaby więcej niż K. Oczywiście Ola teoretycznie mogłaby jechać przepisowo, ale to tylko teoria…

Wiadomo, że między każdymi dwoma skrzyżowaniami w mieście Oli istnieje dokładnie jedna trasa. Na każdym odcinku drogi może obowiązywać inny limit prędkości oraz inna wysokość maksymalnego mandatu.

Napisz program, który: wczyta opis miasta Oli, jej budżet oraz zapytania, dla każdego zapytania wyznaczy czas optymalnej podróży między skrzyżowaniami i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N i K – liczba skrzyżowań w mieście oraz maksymalna suma mandatów jaką jest w stanie zapłacić Ola w ciągu jednej podróży.

W każdym z kolejnych N − 1 wierszy znajduje się pięć liczb pooddzielanych pojedynczymi odstępami: a_i, b_i czyli numery połączonych skrzyżowań, d_i – długość odcinka drogi, l_i – limit prędkości obowiązujący na danej ulicy (taki sam w obie strony) oraz m – maksymalna wysokość mandatu jaką można dostać na tym odcinku drogi (za jazdę z prędkością równą dwukrotności limitu prędkości).

W kolejnym wierszu jest jedna liczba naturalna Q – liczba zapytań. Każde zapytanie znajduje się w osobnej linii i jest zadane przez parę liczb u_i i v_i, oznaczających numery skrzyżowań między którymi Ola chciałby jak najszybciej przejechać.

Skrzyżowania numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie.

Wyjście

W i-tym wierszu odpowiedzi ma się znaleźć minimalna ilość czasu potrzebna na przejazd pomiędzy miastami u_i oraz v_i, przy ustalonym budżecie K.

Odpowiedź zostanie zaakceptowana jeśli będzie się różnić od poprawnej o nie więcej niż 10⁻⁶.

Ograniczenia

1 ≤ N, Q ≤ 50 000, 0 ≤ K ≤ 10⁶, 1 ≤ d_i, l_i, m_i ≤ 1 000.

Przykład

6 8.0
1 2 5.0 1.0 2.0
2 3 5.0 1.0 2.0
2 4 5.0 1.0 2.0
1 5 5.0 1.0 2.0
5 6 5.0 1.0 2.0
4
1 3
2 5
1 5
4 6

5.000000000
5.000000000
2.500000000
10.000000000