POLSKI SPOJ

Arek i Jarek postanowili urządzić sobie wyścig. Miejscem ich wyścigu będzie kraj w którym znajduje się n miast. W niektórych miastach są postawione portale, dzięki którym istnieje m połączeń umożliwiających teleportację między parami miast. Arek znajduje się w mieście X, Jarek w mieście Y, a metą jest miasto Z. Jednak aby używać portali niezbędny jest pluton. Przed całym wyścigiem, Jarek i Arek muszą sobie wylosować, liczbę oznaczającą ilość plutonu jaka będzie im dostarczana co godzinę w trakcie wyścigu. Arek losuje liczbę całkowitą z przedziału [a..b], a Jarek liczbę całkowitą z przedziału [c..d]. Szanse na wylosowanie każdej liczby są takie same. Zwycięzcą wyścigu jest ten który pierwszy przybędzie na metę. Remis nie jest wygraną.

Jarek bardzo poważnie podchodzi do tego wyścigu i zależy mu na wygranej, dlatego zastanawia się nad nielegalnym kupnem kopani plutonu, która dostarczałaby mu co godzinę dodatkowy pluton. Wylosowane wartości oznaczające ilość otrzymywanego plutonu co godzinę nie są mu jeszcze znane, dlatego nie wie ile dodatkowego plutonu potrzebuje. Zna za to rozkład miast i połączeń umożliwiających teleportację, koszt użycia konkretnych portali, a także miasta X, Y i Z. Zna również liczby a, b, c i d. Zastanawia się teraz, ile dodatkowego plutonu musiałby dostawać co turę, aby szanse na jego wygraną były niemniejsze niż x ?

Napisz program który wczyta opis kraju (ilość miast, połączenia umożliwiające teleportację i koszt ich wykorzystania), wczyta liczbyX, Y i Z będące indeksami miast, oraz liczby a, b, c i d, a następnie odpowie na q zapytań: ile minimalnie dodatkowego plutonu musiałby dostawać co godzinę Jarek, aby szanse na jego wygraną były niemniejsze niż x% ?

Wejście

W pierwszej linii wejścia znajduje się dziewięć liczb: n, m, X, Y, Z, a, b, c, d.

W każdej z następnych m lini znajdują się trzy liczby, u, v, w, oznaczające że istnieje połączenie umożliwiające teleportację z miasta u do miasta v i wymaga ono zużycia w plutonu.

W następnej lini znajduje się liczba q oznaczająca ilość zapytań.

W każdej z następnych q linii znajduje się jedna liczba zmiennoprzecinkowa x.

Wyjście

Dla każdego zapytania należy wypisać liczbę oznaczającą minimalną ilość plutonu, którą w trakcie wyścigu co godzinę musiałby dostawać Jarek, aby jego szansę na wygraną były niemniejsze niż x% ? Jeśli nie jest możliwe uzyskanie takich szans, należy wpisać -1.

Ograniczenia

3 ≤ n ≤ 10⁵.

1 ≤ m ≤ 2*10⁵.

1 ≤ X, Y, Z ≤ n.

X ≠ Y, X ≠ Z, Y ≠ Z.

1 ≤ a ≤ b ≤ 10^7.

1 ≤ c ≤ d ≤ 10⁷.

1 ≤ u, v ≤ n.

1 ≤ w ≤ 10⁷.

1 ≤ q ≤ 10⁴.

0 ≤ x ≤ 100. Liczba x będzie zawierała maksymalnie 8 liczb po przecinku.

Przykład 1

Wejście:
3 2 1 2 3 1 3 1 3
1 3 3
2 3 3
5
30
40
55.5555
55.55555556
90

Wyjście:
0
1
1
2
-1
Przykład 2
Wejście:
10 15 7 1 10 5 27 1 12
1 10 4537
3 9 3012
3 9 8766
8 4 7683
8 3 9356
10 7 5352
7 4 1330
3 10 5256
4 10 3194
1 4 1023
3 6 5546
5 10 440
10 3 9792
7 2 1692
9 1 9476
10
79.72
24.7842
23
51.5608
12.6981
18.224
59.18
89.081
19.1247
27.4913
Wyjście:
15
4
3
9
0
2
11
18
2
4
15