Observing the Tree

All submissions for this problem are available.
Chef gives you a tree, consisting of N nodes. The nodes are numbered from 1 to N, and each node has an integer, which is equal to 0 initially. Then, Chef asks you to perform M queries.
The first type of queries is changing: here, you are given integers X, Y, A and B. Add A to the integer, associated with the node X, then add A+B to the integer, associated with the second node on the way from X to Y, then add A+2*B to the integer, associated with the third node on the way from X to Y, and so on. As you know, there is only one simple path from X to Y.
The second type of queries is a question: here, you are given integers X and Y. Output the sum of all integers, associated with nodes on the way from X to Y.
The third type of queries is a rollback: here, you are given an integer X. All the integers associated with the nodes return to the state after the Xth changing query. If X is 0, then all of them become equal to zero, as in the very beginning.
Input
The first line of an input consists of two integers  N and M.
Then, N−1 lines follow. These N−1 lines describe the tree structure. Each line consists of two integers  X and Y, and that means that there is an edge between node X and node Y.
Then, M lines follow. A single line denotes a single query, which has one of the following forms: (See the sample for the detailed explanation)
 c X_{1} Y_{1} A B  changing query,
 q X_{1} Y_{1}  question query,
 l X_{1}  rollback query.
As you can see, the numbers X and Y aren't given to you directly. For the rollback query, actual number X will be equal to (X_{1}+lastans) modulo (total number of changing queries before this query + 1). For the changing and question queries, X will be equal to ((X_{1}+lastans) modulo N)+1 and Y will be equal to ((Y_{1}+lastans) modulo N)+1, where lastans denotes the last number that you have output, or zero if you haven't output any numbers yet.
Output
For each question query output the answer on a single line.
Constraints
 1 ≤ N, M ≤ 100000 (10^{5})
 0 ≤ A, B ≤ 1000
 0 ≤ X_{1}, Y_{1} ≤ 100000 (10^{5})
Example
Input: 5 7 1 2 2 3 3 4 4 5 c 1 4 2 3 c 2 3 5 10 q 1 3 l 1 q 1 3 l 1 q 1 3 Output: 35 0 15
Explanation
As you can see, the tree in the sample is like a line. Let's denote the first state of integers 0 0 0 0 0, where the ith integer means the integer associated with the node i.
In the first changing query "c 1 4 2 3", the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (4 + 0) modulo 5 + 1 = 5. Hence the state will be 0 2 5 8 11 after this query.
After the second changing query "c 2 3 5 10", the state will be 0 2 10 23 11 for similar reason.
In the next question query, the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (3 + 0) modulo 5 + 1 = 4. Hence the answer must be 2 + 10 + 23 = 35.
In the first rollback query "l 1", the actual number is X = (1 + 35) modulo (2 + 1) = 36 modulo 3 = 0, since lastans = 36. Thus the state will be rollbacked to 0 0 0 0 0.
Then the answer of the next question query "q 1 3" must be 0, because all integers are currently 0.
In the second rollback query "l 1", the actual number is X = (1 + 0) modulo (2 + 1) = 1, since lastans = 0. Thus the state will be 0 2 5 8 11, which is the state after the first changing query.
Then the answer of the last question query must be 2 + 5 + 8 = 15.
Author:  xcwgf666 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/QUERY 
Tags  feb13, hard, heavylight, persistence, xcwgf666 
Date Added:  26122012 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 