{"raw_statement":[{"iden":"statement","content":"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. \n\nPaul has m employees. The i'th employee has an order to deliver rackets from place ai to place bi, making one trip from place ai to place bi every day, from day si to day ti inclusive.\n\nPaul'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. \n\nPaul 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 cj to day dj inclusive. Send help.\n\nThe first line of input contains two space-separated integers n, m, and q (2 ≤ n ≤ 105 and 1 ≤ m, q ≤ 105), the number of places, employees, and queries respectively.\n\nEach 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. \n\nEach of the next m lines of input contains four space-separated integers ai, bi, si, and ti (1 ≤ ai, bi ≤ n and 1 ≤ si ≤ ti ≤ 109), representing the order for the i'th employee. It is guaranteed that ai ≠ bi.\n\nEach of the next q lines of input contains two space-separated integers cj and dj (1 ≤ cj ≤ dj ≤ 109), representing Paul's j'th query. \n\nThe 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).\n\n"},{"iden":"input","content":"The first line of input contains two space-separated integers n, m, and q (2 ≤ n ≤ 105 and 1 ≤ m, q ≤ 105), 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 ai, bi, si, and ti (1 ≤ ai, bi ≤ n and 1 ≤ si ≤ ti ≤ 109), representing the order for the i'th employee. It is guaranteed that ai ≠ bi.Each of the next q lines of input contains two space-separated integers cj and dj (1 ≤ cj ≤ dj ≤ 109), representing Paul's j'th query. "},{"iden":"output","content":"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)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ denote the number of places, employees, and queries, respectively.  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $, where each edge $ e_j \\in E $ represents a bidirectional road.  \nLet $ E = \\{e_1, e_2, \\dots, e_{n-1}\\} $.  \nLet $ \\mathcal{E} = \\{(a_i, b_i, s_i, t_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the set of employee orders, where each employee $ i $ travels the unique path from $ a_i $ to $ b_i $ on days $ s_i $ to $ t_i $ inclusive.  \nFor each edge $ e_j $, define its *active interval* as the set of days during which at least one employee uses it:  \n$$\nI_j = \\bigcup_{\\substack{i=1 \\\\ e_j \\in \\text{path}(a_i, b_i)}}^{m} [s_i, t_i]\n$$  \nLet $ f_j(d) = \\mathbf{1}_{d \\in I_j} $ be the indicator that edge $ e_j $ is used on day $ d $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 10^5 $, $ 1 \\le m, q \\le 10^5 $  \n2. $ 1 \\le a_i, b_i \\le n $, $ a_i \\ne b_i $  \n3. $ 1 \\le s_i \\le t_i \\le 10^9 $  \n4. $ 1 \\le c_j \\le d_j \\le 10^9 $ for each query  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute the total toll cost over days $ [c_j, d_j] $:  \n$$\n\\text{Cost}_j = \\sum_{d = c_j}^{d_j} \\sum_{e_j \\in E} f_j(d) = \\sum_{e_j \\in E} \\left| I_j \\cap [c_j, d_j] \\right|\n$$","simple_statement":"Paul delivers badminton rackets between n places connected by n−1 roads (a tree).  \nHe has m employees. Each employee i delivers from place a_i to b_i every day from s_i to t_i.  \nEach road costs $1 per day if any employee uses it that day (only paid once per day, even if multiple use it).  \nYou get q queries. For each query [c_j, d_j], find total cost from day c_j to d_j.","has_page_source":false}