Fibonacci Numbers on Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In mathematical terms, the sequence F[N] of Fibonacci numbers is defined by the recurrence relation F[N] = F[N1] + F[N2], with seed values F[1] = 1,F[2] = 1.
Today, Chef gives you a rooted tree, consisting of N nodes. At first, the node 1 is the root. The nodes are numbered from 1 to N, and each node has an integer that initially equals to 0. Then, Chef asks you to perform M queries.
The queries are as follows:

A x y

QS x y

QC x y

R x
Add F[1] to the integer, associated with the node x, then add F[2] to the integer, associated with the second node on the way from x to y, then add F[3] 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.
Let node x be the root of the tree, output the sum of all integers, associated with the nodes in the subtree of the node y, modulo 1000000009(10^{9}+9).
Output the sum of all the integers, associated with the nodes on the way from x to y, modulo 1000000009(10^{9}+9).
All the integers associated with the nodes return to the state after the xth query. If x is 0, then all of them become equal to 0, as in the very beginning.
Input
 A x_{1} y
 QS x_{1} y
 QC x_{1} y
 R x_{1}
The first line of the input consists of two space separated intergers  N and M respectively.
Then, N1 lines follow. These N1 lines describe the tree structure. Each line consists of two intergers  x and y, and that means that there is an edge between the node x and the node y.
Then, M lines follow. Every single line denotes a single query, which has one of the following forms: (See the sample for the detailed explanation)
As you can see, the number x isn't given to you directly. For all queries, actual number x will be equal to x_{1} xor lastans, where lastans denotes the last number that you have output, or 0 if you haven't output any numbers yet.
Output
For each query of the type QS or QC, output the answer modulo 10^{9}+9
Constraints
 1 ≤ N, M ≤ 100000
 1 ≤ x, y ≤ N
Example
Input: 5 6 1 2 1 3 3 4 3 5 A 4 2 A 2 5 QS 4 3 QC 12 4 R 6 QC 6 4 Output: 13 7 4
Explanation
Let’s denote the first state of integers as 0 0 0 0 0, where the ith interger means the integer associated with the node i.
In the first query “A 4 2”, the actual number is x = 4 xor 0 = 4. Hence the state will be 2 3 1 1 0 after this query.
After the second query “A 2 5”, the state will be 3 4 3 1 3 for the similar reason.
In the next query, the answer is 3+4+3+3=13.
In the next query, the actual number is x = 12 xor 13 = 1, the answer is 3+3+1=7.
In the query “R 6”, the actual number is x = 6 xor 7 = 1, the state will be roll backed to 2 3 1 1 0.
At last, the actual number is x = 6 xor 7 = 1, the answer is 2+1+1=4.
Author:  dzy493941464 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FIBTREE 
Tags  dzy493941464, hard, heavylight, math, persistence, segmenttree, sept14 
Date Added:  25062014 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, PERL6, TEXT, 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. 