JOI Kingdom: Maximizing Gold Retention

There are $$N$$ cities in JOI Kingdom connected by $$N-1$$ roads. The roads form a tree structure so that one can travel between any pair of cities. Some roads have checkpoints. There are $$M$$ checkpoints in total, where the $$j^{th}$$ checkpoint is located on road $$P_j$$ and requires either 1 gold coin or $$C_j$$ silver coins to pass.

In addition, there are $$Q$$ citizens. The $$k^{th}$$ citizen starts at city $$S_k$$ with $$X_k$$ gold coins and $$Y_k$$ silver coins and wishes to travel to city $$T_k$$. Since gold coins are valuable, the citizen wants to keep as many gold coins as possible. On each checkpoint along the unique path from $$S_k$$ to $$T_k$$, the traveler can choose to pay with silver coins (costing $$C_j$$ coins) if available, otherwise they must pay 1 gold coin.

Your task is to determine, for each citizen, whether it is possible to complete the journey, and if so, calculate the maximum number of gold coins that can be retained after paying the required tolls.

inputFormat

The input consists of the following:

• Line 1: Three integers $$N$$, $$M$$, $$Q$$.
• Next $$N-1$$ lines: Each line contains two integers $$A_i$$ and $$B_i$$ indicating that there is a road connecting city $$A_i$$ and city $$B_i$$. The roads are numbered from 1 to $$N-1$$ in the order they are given.
• Next $$M$$ lines: Each line contains two integers $$P_j$$ and $$C_j$$. The checkpoint $$j$$ is located on road $$P_j$$ and requires $$C_j$$ silver coins if chosen instead of paying 1 gold coin.
• Next $$Q$$ lines: Each line contains four integers $$S_k$$, $$T_k$$, $$X_k$$, and $$Y_k$$. Here, $$S_k$$ is the starting city, $$T_k$$ is the destination, $$X_k$$ is the number of gold coins, and $$Y_k$$ is the number of silver coins the citizen has.

outputFormat

For each query, output a single line with one integer. If it is impossible for the citizen to travel from $$S_k$$ to $$T_k$$ given the coin constraints, output -1. Otherwise, output the maximum number of gold coins the citizen can retain after paying the tolls along the path.

sample

5 3 3
1 2
2 3
2 4
1 5
2 5
3 2
1 3
3 4 1 10
5 3 2 3
4 3 0 10

1
1
0