It is exam season at UTS, and the air is thick with the excitement of students preparing for their valiant battles against French words and comparative essays. In such a charged atmosphere, all sorts of shocking education-related events are occurring throughout the building on a regular basis.
Now, one should know that the UTS students love to spread this juicy academic gossip. In fact, their dedication to the activity is so great that they have set up a tree-shaped network to facilitate its spread, with each student represented by a node in the network.
When a student announces some piece of news, it spreads throughout the gossip network. The student has popularity , and any news that he/she passes on will have its interest value multiplied by . This means that student starts some gossip with interest value , when student hears it, it will have an interest value of , where is the product of the popularities of all students on the path from to (The popularity of student is not included in the product).
In order to maintain absolute control over all students' social lives, Principal Evans likes to be able to track the status of the network at all times.
There are two types of queries:
1 s v: Student announces some news of interest value .
2 s: Find the sum of the interest values of all the news that student heard, including news that originated with . Output this number modulo .
The first line contains and , the number of students and the number of queries.
The second line contains integers , the popularities of the students.
The next lines contain two integers , indicating that there is an edge in the network between students and . It is guaranteed that the input describes a valid tree.
Each of the next lines contains a valid query in the format specified above.
For each type 2 query, output the answer on a separate line.
Subtask 1 [20%]
Subtask 2 [30%]
The network is a straight path, where student is connected to students and , for all . (1 and are the endpoints of the path)
Subtask 3 [50%]
Sample Input 1
3 3 2 5 4 1 2 2 3 1 1 3 2 3 2 1
Sample Output 1
Explanation for Sample Output 1
A piece of news with interest value originates at student . When he/she tells it to student , it's interest gets multiplied by . When student tells it to student 3, it gets multiplied by . Thus, student 3 hears news with interest value .
To student , the news has interest value , because it was never multiplied by anyone's popularity.