A lot of big storms.
Warm air and cold air don't mix very nicely – because whenever they do, storms tend to follow.
Your job, as a Turbulent Location Estimator, is to track their movement.
Air currents in your area can be mapped into
nodes and
air channels.
Initially, there is one warm air body at node
and one cold air body at node
.
Each channel connects two distinct nodes
and
with a traverse time of
.
All channels are bidirectional and have a confined path. No two nodes will have more than one channel connecting them.
Air bodies naturally expand.
So, they may intersect at nodes, or even on channels!
Wherever this occurs, the present air bodies cannot pass through each other.
However, if this occurs on a node that connects to other unoccupied channels, then the present air bodies can continue to spread to those channels simultaneously alongside each other.
You have been given
queries, each asking for
: the exact time when a storm occurs at a particular location.
It is possible to reach any node from any other node.
Have you got what it takes for the job?
Constraints




Note: It is possible to have
.
Subtask |
Percentage |
Additional Constraints |
 |
 |
,  |
 |
 |
,  |
 |
 |
,  |
 |
 |
No additional constraints. |
Input Specification
The first line contains four spaced integers:
,
,
, and
.
The following
lines each contain three spaced integers:
,
, and
.
The next line contains integer
.
The following
lines each contain two spaced integers:
and
.
If
, then
is the number of a node
.
If
, then
is the number of a channel
.
Channel numbers appear in order in the input, starting at
.
Output Specification
For each query, output
on its own line.
Time starts at
.
If a storm does not exist at that location, output -1
.
Your answer will be judged as correct if it is within an absolute error of
.
Sample Input
Copy
7 7 1 3
1 2 6
1 5 7
2 3 6
2 6 5
3 4 1
4 5 3
5 7 8
5
1 2
1 5
1 6
2 2
2 4
Sample Output
Copy
6
-1
11
5.5
6
Explanation
The warm air body starts at node
while the cool air body starts at node
.
They both spread to reach node
at the same time, causing a storm there at
.
Then, they both simultaneously spread alongside each other to node
at
.
Note that storms occur along the entire path of channel
, so we take the earliest incidence time as
(rounded from a time negligibly greater than
).
Meanwhile, the cool air body reaches node
first, spreading to node
and
.
It essentially blocks off the warm air body's path to node
.
Thus, both bodies of air directly collide on channel
at
.
Comments