G. Ifrit Tile
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Waymo has been playing too much Arknights. Now he looks for rows of 6 in every gridlike structure he finds and has the urge to commit arson using child lab...

The Rhodes Island operators are scouting out the new map for CCB#2. The map can be represented as a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Slugs of $$$m$$$ different colors exist, and there is one slug of color $$$i$$$ ($$$1 \le i \le m$$$) for each node on the shortest path from $$$s_i$$$ to $$$t_i$$$. Note that multiple slugs of different colors can be on the same node, and not all colors of slugs are initially on the map.

The slugs have a very particular behavior pattern where sometimes all the slugs of the same color will leave the map, or all the slugs of the same color will return to the map.

Ifrit is tasked with clearing out the slugs, so she will consider different plans of attack. A plan of attack is denoted by two nodes $$$u$$$ and $$$v$$$ in which she hits all the slugs on the shortest path from $$$u$$$ to $$$v$$$. If she hits any slug with color $$$i$$$, she adds $$$v_i$$$ to her score, where $$$v_i$$$ is a predetermined value for color $$$i$$$. Ifrit will not actually perform the attack, but she wants to know her score for each plan of attack.

You will have to process $$$q$$$ events, each one of the following three types:

  1. All the slugs of color $$$i$$$ return to their respective nodes on the tree.
  2. All the slugs of color $$$i$$$ leave the tree.
  3. Calculate the score Ifrit would achieve if she performed an attack by selecting nodes $$$u$$$ and $$$v$$$.
Input

The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ $$$(1 \leq n, m, q \leq 3 \cdot 10^5)$$$ — the number of nodes in the tree, the number of colors, and the number of events respectively.

The following $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$, denoting an edge between nodes $$$u$$$ to $$$v$$$ in the tree. It is guaranteed that the inputted set of edges forms a valid tree.

The following $$$m$$$ lines each contain four integers $$$s_i$$$, $$$t_i$$$, $$$v_i$$$, and $$$c_i$$$ $$$(1 \leq s_i, t_i \leq n, 1 \leq v_i \leq 10^9, c_i \in \{0, 1\})$$$ — the start and end of the shortest path the slugs of the $$$i$$$-th color reside on, the value of hitting color $$$i$$$, and whether or not the slugs of color $$$i$$$ are present initially. If $$$c_i = 0$$$, they are not present; otherwise, if $$$c_i = 1$$$, they are.

The following $$$q$$$ lines outline events, each in one of the following formats:

  • $$$1 \ i$$$ $$$(1 \leq i \leq m)$$$ — all the slugs of color $$$i$$$ return to the map. It is guaranteed that they were not present on the map before this event.
  • $$$2 \ i$$$ $$$(1 \leq i \leq m)$$$ — all the slugs of color $$$i$$$ leave the map. It is guaranteed that they were present on the map before this event.
  • $$$3 \ u \ v$$$ $$$(1 \leq u, v \leq n)$$$ — Ifrit is considering an attack plan of $$$u$$$ and $$$v$$$ and wants to know her score if she were to follow that plan. Note that Ifrit will not actually attack anything.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1 - 2$$$ satisfy $$$n, m, q \leq 100$$$.

Tests $$$3 - 5$$$ satisfy $$$n, m, q \leq 1000$$$.

Tests $$$6 - 12$$$ satisfy $$$v_i = 1$$$ for all $$$i$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each attack plan (event of type $$$3$$$), output the score Ifrit will get if she follows the plan.

Examples
Input
5 3 9
1 2
1 3
2 4
2 5
3 4 1 0
2 5 10 0
1 4 100 0
1 1
3 5 3
1 2
3 1 4
1 3
3 1 5
2 1
3 5 3
3 5 5
Output
1
11
111
110
10
Input
10 4 12
2 10
3 6
4 3
7 9
7 5
5 4
1 5
10 1
10 8
9 9 18 0
3 6 47 0
2 4 91 0
3 3 30 1
1 1
3 6 4
1 2
3 1 5
2 4
3 5 10
3 6 2
3 3 9
3 10 8
1 4
3 3 3
1 3
Output
30
0
0
47
65
0
77
Note

—

Problem Idea: willy108, hyforces

Problem Preparation: willy108

Occurrences: Advanced G