406232: GYM102319 B Paul's Badminton

Paul is running a quaint business that delivers badminton rackets. There are n places of interest between which he will deliver rackets. These n places are connected by only n - 1 bidirectional roads because Paul's country does not believe in roads.

Paul has m employees. The i'th employee has an order to deliver rackets from place a_i to place b_i, making one trip from place a_i to place b_i every day, from day s_i to day t_i inclusive.

Paul's country believes in tolls. Every day, if any of Paul's employees uses the j'th road, Paul must pay an exorbitant toll of $1 for that road. Fortunately, each toll must only be paid once per day. In other words, if Paul pays the toll for road j for some day, then any number of his employees may use that road during that day with no extra cost.

Paul wants to know some details on the amount of money he needs to pay for these tolls, so he gives you q queries. For the jth query, he asks you how much money he needs to pay from day c_j to day d_j inclusive. Send help.

The first line of input contains two space-separated integers n, m, and q (2 ≤ n ≤ 10⁵ and 1 ≤ m, q ≤ 10⁵), the number of places, employees, and queries respectively.

Each of the next n - 1 lines of input contains two space-separated integers x and y (1 ≤ x, y ≤ n), which means that there is a road connecting places x and y.

Each of the next m lines of input contains four space-separated integers a_i, b_i, s_i, and t_i (1 ≤ a_i, b_i ≤ n and 1 ≤ s_i ≤ t_i ≤ 10⁹), representing the order for the i'th employee. It is guaranteed that a_i ≠ b_i.

Each of the next q lines of input contains two space-separated integers c_j and d_j (1 ≤ c_j ≤ d_j ≤ 10⁹), representing Paul's j'th query.

The output should contain q lines. The j'th line should contain a single integer which is the answer to the j'th query (in the order given in the input).

5 3 3
1 2
3 2
1 4
1 5
2 5 4 7
3 4 2 5
2 3 6 9
7 11
3 6
5 5

5
14
4