408869: GYM103366 I Homework

Cirno is a strict teacher, while Wings is a naughty student.

Cirno assigns a huge amount of homework to $$$n$$$ of her students, including Wings every day. Wings wants to finish the homework as soon as possible. He calls on the classmates to copy homework from each other. Due to the different abilities of these students, the time it takes for each to finish the homework independently may be different. After discussion, in order to make everyone finish the homework as soon as possible, these students developed a solution: one can ask other who has finished the homework for answers and then just copy that. Cirno is too strict with her students, she has confiscated all the Internet-capable devices of her students, so these students must copy the homework in a more primitive way — going to another student's home.

There are $$$n-1$$$ bidirectional roads between the homes of $$$n$$$ students and each road connects two students' homes. Any two students can reach each other's home directly or indirectly. If student $$$i$$$ intends to copy student $$$j$$$'s homework, he or she must wait for student $$$j$$$ to finish the homework, then leaves for student $$$j$$$'s home and copies the homework, and finally returns home (The homework is considered to be finished only when the student returns home). The time taken for student $$$i$$$ to leave for student $$$j$$$'s home, copy the homework, and finally return home equals to the distance between student $$$i$$$'s home and student $$$j$$$'s home.

Soon, Cirno discovered Wings's tricks. She was very angry, so she planned to calculate the earliest time for each student to finish the homework, and increase the amount of homework according to the situation as a punishment. However, the students' learning status and the road lengths will change. Cirno asks you to help her to calculate the earliest time for each student to finish the homework in different situation.

The first line contains two positive integers $$$n, q$$$ ($$$1 \le n, q \le 10^5$$$). $$$n$$$ denotes the number of students. $$$q$$$ denotes the total number of changes and queries.

The next line contains $$$n$$$ space separated integers $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$), denoting the time for student $$$i$$$ to finish the homework independently.

The next $$$n-1$$$ lines contain the description of roads between students' homes. Each line contains three integers $$$u, v, w$$$ ($$$1 \le u, v \le n, 0 \le w \le 10^9$$$), denoting that there is a road with length $$$w$$$, connecting student $$$u$$$'s home and student $$$v$$$'s home.

The next $$$q$$$ lines contain descriptions of changes and queries. Each line describes one type of change or a single query.

The first type of change is described by three integers $$$op, i, x$$$ ($$$op = 1, 1 \le i \le n, 0 \le x \le 10^9$$$), which means the time for student $$$i$$$ to finish the homework independently changes to $$$x$$$;

The second type of change is described by three integers $$$op, i, w$$$ ($$$op = 2, 1 \le i < n, 0 \le w \le 10^9$$$), which means the length of the $$$i$$$-th road in the input changes to $$$w$$$.

The query is described by one integer $$$op$$$ ($$$op = 3$$$), which means you need to calculate the earliest time for each student to finish the homework.

It's guaranteed that any two students can reach each other's home directly or indirectly. And it's guaranteed that the number of queries does not exceed $$$200$$$.

For each query, print an integer in one line. Let $$$t_i$$$ denotes the earliest time for student $$$i$$$ to finish the homework. The integer you need to print is $$$t_1 \oplus t_2 \oplus \dots \oplus t_n$$$ ($$$\oplus$$$ denotes the bitwise XOR operation).

4 5
4 4 2 7
2 1 8
3 1 9
4 3 1
3
1 1 1
3
2 1 1
3

1
4
2

For the first query, student $$$1$$$, student $$$2$$$ and student $$$3$$$ finish their homework independently, and the times are $$$t_1 = 4$$$, $$$t_2 = 4$$$, $$$t_3 = 2$$$. Student $$$4$$$ goes to student $$$3$$$'s home after student $$$3$$$ finished the homework to copy homework. The time for student $$$4$$$ to finish the homework is $$$t_4 = 2 + 1 = 3$$$.

For the second query, the earliest times for the four students to finish the homework are $$$t_1 = 1$$$, $$$t_2 = 4$$$, $$$t_3 = 2$$$, $$$t_4 = 3$$$.

For the second query, the earliest times for the four students to finish the homework are $$$t_1 = 1$$$, $$$t_2 = 2$$$, $$$t_3 = 2$$$, $$$t_4 = 3$$$.