Tree Color and Weight Maintenance

You are given a tree with \( n \) nodes numbered from \( 1 \) to \( n \). Initially, each node \( i \) has a weight \( a_i = 0 \) and a color \( c_i \). You need to process \( m \) operations on the tree. There are three types of operations:

• 1 x y c: Change the color of every node on the shortest path between nodes \( x \) and \( y \) to \( c \).
• 2 x w: In the connected component (based on the current colors) that contains node \( x \), add \( w \) to the weight of every node. (Two nodes are considered connected if there is a path between them and all nodes along the path have the same color.)
• 3 x: Query the weight of node \( x \).

Note: The unique path between any two nodes in the tree is used in operation 1. Also, for operation 2, the maximally connected component is defined as the set of nodes which can reach each other and share the same color.

inputFormat

The first line contains two integers \( n \) and \( m \) - the number of nodes and the number of operations.

The second line contains \( n \) integers \( c_1, c_2, \ldots, c_n \) representing the initial color of each node.

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) representing an edge between nodes \( u \) and \( v \) (which forms a tree).

Each of the following \( m \) lines describes an operation in one of the following formats:

• 1 x y c
• 2 x w
• 3 x

outputFormat

For each operation of type 3 x, output the current weight of node \( x \) on a new line.

sample

5 5
1 2 1 2 1
1 2
1 3
2 4
2 5
3 1
2 1 10
3 3
1 3 5 2
2 4 5

0
10