Four Friends

Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Paavini, Nupur, Anchal and Ishita are four best friends and roommates. In their normal routine, they only study and study and do nothing else. But now that exams are over, they want to explore the town, so they went to the Trade Fair to eat.
The trade fair has N halls and it's represented by a tree with N vertices and N1 edges. Each edge contains exactly one restaurant offering only meals of one type at a fixed cost.
Since Bhavya and Kaushal didn't go along with them, they have asked Q queries. Each query is given as follows: The friends move from hall U to hall V along the shortest path. From each restaurant they encounter on this path, they will purchase exactly one meal in total if its cost C satisfies the following conditions:
 If C is a multiple of 2, C must be between X_{1} and Y_{1} inclusive.
 If C is a multiple of 3, C must be between X_{2} and Y_{2} inclusive.
 If C is a multiple of 5, C must be between X_{3} and Y_{3} inclusive.
 C must be a multiple of 2, 3 or 5.
For each query, compute the total cost of all meals bought when travelling from U to V. you have the answer the queries in online mode.
Input
 U = in_{1} + last
 V = in_{2} + last
 X_{1} = in_{3} + last
 Y_{1} = in_{4} + last
 X_{2} = in_{5} + last
 Y_{2} = in_{6} + last
 X_{3} = in_{7} + last
 Y_{3} = in_{8} + last
Output
For each query, print the answer to it on a separate line.
Constraints
 1 ≤ N, Q ≤ 50,000
 1 ≤ U, V ≤ N
 1 ≤ C ≤ 40,000
 1 ≤ X_{i} ≤ Y _{i} ≤ 40,000, for each 1 ≤ i ≤ 3
Subtasks
Subtask #1 (20 points): 1 ≤ N, Q ≤ 1000
Subtask #2 (80 points): original constraints
Example
Input: 3 2 1 2 6 1 3 11 2 3 2 20 3 20 2 4 4 3 4 14 3 1 4 2 Output: 6 0
Explanation
For the first query, they will eat at the restaurant connecting halls 1 and 2; the cost of the meal there is 6.
For the second query, 6 is a multiple of 3, but according to the second condition, the cost of this meal isn't between 3 and 5. Hence they will not eat at any restaurant.
Author:  abx_2109 
Tags  abx_2109, binarysearch, dfs, inclusionexclusion, lca, ltime55, mediumhard 
Date Added:  27112017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions