Easy Airthmetic Geometric Progression

All submissions for this problem are available.
In planet Krypton, the people use concalls to communicate with each other. The concall network is composed of concall devices connected to each other. The network is such that from each concall device, there is a unique path through the network to reach every other concall device.
An Edit: Note that, the connection between any two concall devices, if connected, is two way.
The network has a parameter R, constant for it throughout its use. Every concall device has some value associated with it, which is initially zero.
General Zod, a militant leader, knows that the concall network is the lifeline of the society in the planet and so wishes to slowly poison it. To do this, he introduces nanomites in the network, through a stateoftheart program.
Whenever he runs the program on devices A and B, then all devices in the shortest path from A to B have their value incremented by a certain amount by the nanomites. The amount incremented of nodes in the path is in arithmetic geometric series, i.e., if the shortest path is A, V_{1}, V_{2},.....,B, then value of A is incremented by XR^{1}, value of V_{1} is incremented by 2XR^{2}, value of V_{2} is incremented by 3XR^{3} and so on. The value of X can be different for every program run by Zod while the value of R is fixed for the network, as specified earlier.
After having run the program to change the values in the specified way of multiple devices in the network, General Zod wishes to make some queries of the values of the network to assess the correctness of his program. He wants to know that, given two devices C and D, what is now the sum of values of devices in the shortest path from C to D. Since this value may be very large, you have to report it modulo 100711433.
Input Format
First line contains two integers (N and R respectively) separated by space.
In the next N1 lines, each line contains two integers A and B, such that there is a direct connection between A and B.
Next line contains two space separated Integers (U and Q respectively) representing the total number of Update and Query operations to follow.
Next U lines follow each line asking to increment the value of certain nodes in the above specified way. Each line contains 3 space specified integers, X, A and B, where X is the parameter for the program and A and B are the devices, such that values of all devices between A and B are to be updated.
Next Q lines, each line containing two integers C and D.
Output Format
Output the answer to each query as explained.
Constraints
 1 ≤ R ≤ 10^{9}
 1 ≤ N ≤ 10^{5}
 1 ≤ U ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ X ≤ 10^{9}
Sample Input
5 2
1 2
2 3
2 4
1 5
2 2
3 3 4
3 2 5
3 4
2 5
Sample Output
108
126
Explanation
Value of R is 2.
After first update the values of device 3 becomes 6, device 2 becomes 24, device 4 becomes 72.
After second update values of device 2 becomes 24+6=30, device 1 becomes 24, device 5 becomes 72.
For first query operation, Value[3] + Value[2] + Value[4] = 108
For second query operation, Value[2] + Value[1] + Value[5] = 126
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions