Power Tower

All submissions for this problem are available.
There are multiple parallel universe and one can traverse from one to another using the method of inception. A universe is reachable from another only if they are connected by an "inception line", and for two universe not connected by a direct "inception line", one might have to traverse multiple intermediate universe before reaching the destination universe. You are assured there will be exactly one path from any universe to any other.
However there's another catch for the people planning to traverse between different universe. Every universe has a time factor associated with it. Given two universe A and B with a direct "inception line" between them, assume A has a time factor S and B has a time factor T, then a job J in A will be slowed by a S ^{ T } factor in B. Similarly if from B, one moves to another universe C, directly connected to it, having time factor V, then the job will be slowed down by a factor of S ^{ ( T V ) } in C, and so on. Note that it may appear contradictory to common sense, but thats how things in parallel universe are.
You will be given the data of all universe with the connectivity information between them. Your task is, given two universe P and Q, to report the factor by which the job will be slowed down, when one traverses from P to Q. Since this factor can be very large, you will have to report it modulus some value, which will be given in the input. Also the time factor may have to updated and such an operation will also have to be supported. However, there will be atmost 5 update operations.
Input Format
First line contains two space separated integers, N and K.
The next N1 lines contain the connectivity information. Each line contains two space separated integers P and R, representing there is an "inception line" between P and R.
Next line contains N space separated integers, where the ith integer is the value of the time factor for the ith universe.
Following K lines contains the operations to be performed, each line representing an operation.
For a query operation, the first character is Q, followed by three space separated integers A, B and C.
For an update operation, the first character is U, followed by two space separated integer D and E, such the the time factor of universe D is to be changed to E.
Output Format
For each of the query operations, output the factor (mod C) by which a job will be slowed down on traversing from universe A to universe B.
Constraints
 1≤N ≤ 1e5
 1≤K ≤ 1e5
 1≤C ≤ 1e5
 1≤ value of a universe ≤ 1e9
Sample Input
5 5
1 2
2 3
2 4
5 1
2 3 2 2 3
Q 3 4 10000
Q 2 5 10000
U 2 2
Q 3 4 10000
Q 2 5 10000
Sample Output
512
6561
16
256
Explanation
First query operation represents (2^{32}) mod 10000 = 512
Second query operation represents (3^{23}) mod 10000 = 6561
After the update operation, time factor of universe 2 is changed to 2.
Third query operation represents (2^{22}) mod 10000 = 16
Fourth query operation represents (2^{23}) mod 10000 = 256
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  3 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