nodes and
edges. Since it's a tree, there is exactly one path to connect any two nodes. has
weapons and the weapon
can block the path from node
to node
with a cost
. There are
monsters living in the tree. A monster
will travel from node
to node
. can catch a monster if the path he blocks is an exact subpath of the monster's path. can reuse his weapon, and the path is automatically unblocked after he catches a monster. However, thinks this game is not challenging enough. For each monster
, he wants to use the
minimal cost weapon among all the weapons which can catch the monster
. Can you write a program to help him?
Input Specification
The first line contains integers,
,
, and
, which represent the number of nodes, the number of weapons, and the number of monsters, respectively.
Each of the following lines contains
integers,
and
, representing an edge between node
and node
.
Each of the following lines contains
integers,
,
and
(
and
,
), representing a weapon which can block the path from node
to node
with a cost of
.
Each of the following lines contains
integers,
,
and
, representing a monster's path from node
to node
and the
min cost weapon wants to choose. It's guaranteed the
min cost weapon exists.
Output Specification
Output one line for each monster , the
min cost to catch the monster
.
Sample Input 1
6 4 2
1 2
2 3
2 4
3 5
3 6
1 5 2
2 4 3
3 6 5
2 3 4
5 6 1
5 4 2
Sample Output 1
5
4
Sample Input 2
10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 2 2
10 7 1
6 7 4
6 8 5
4 6 6
8 3 3
10 4 10
10 8 9
9 2 7
4 9 8
1 8 5
3 8 3
3 8 4
1 8 3
4 8 1
2 3 1
2 3 1
2 3 1
2 4 1
1 4 1
Sample Output 2
6
5
6
4
4
2
2
2
2
2
Comments