Colored Forest

This problem deals with a dynamic forest (an undirected acyclic graph) on n nodes, numbered from 1 to n. Initially, each node has color 0. You are given q operations of 4 types:

• 1 a b d: Add an edge between nodes a and b with a positive weight d. It is guaranteed that the resulting graph remains a forest.
• 2 a b: Delete the edge between nodes a and b.
• 3 v z k: For the tree containing node v, change the color of all nodes reachable from v by a path whose total weight is at most z to k.
• 4 u: Query the current color of node u.

Note: The distance between two nodes is defined as the sum of the weights along the unique path connecting them. In operation type 3, a node is recolored if its distance from v is \(\le z\). All weights are positive integers.

Your task is to process all q operations in order and output the answer for each query operation (type 4).

inputFormat

The first line contains two integers n and q: the number of nodes and the number of operations.

Each of the following q lines describes an operation in one of the following formats:

• 1 a b d
• 2 a b
• 3 v z k
• 4 u

outputFormat

For each operation of type 4, output a single line with the color of the corresponding node.

sample

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

5
5
0
7
7
7