Dynamic Apple Tree Queries

The problem involves a dynamic apple tree. Initially, there are \(n\) apples numbered from \(1\) to \(n\). These apples are connected by \(n-1\) branches that form a tree. Each apple \(i\) has an initial value \(a_i\) (which may be negative).

During the recording period, there are \(m\) events. The events can be of four types:

• Type 1: 1 u v w — A new apple grows on the branch between apple \(u\) and apple \(v\). Suppose the current number of apples is \(k\). Then, a new apple numbered \(k+1\) with value \(w\) appears. The branch between \(u\) and \(v\) is removed and replaced by two branches: one connecting \(u\) with \(k+1\) and the other connecting \(k+1\) with \(v\).
• Type 2: 2 u w — A new apple grows along with a new branch. A new apple numbered \(k+1\) (if there are currently \(k\) apples) with value \(w\) is added, and a branch is formed that connects apple \(u\) and apple \(k+1\).
• Type 3: 3 u v w — The value of every apple on the unique simple path between apples \(u\) and \(v\) (inclusive) is increased by \(w\). Note that \(w\) may be negative.
• Type 4: 4 u v w — A query. An apple is considered a "premium apple" if its value is at least \(w\). The query asks for the number of premium apples on the simple path between \(u\) and \(v\) (inclusive). This query must be answered online.

Input/Output: You are given the initial tree configuration and the \(m\) events. For every event of type 4, you must output the corresponding result.

inputFormat

The input begins with two integers \(n\) and \(m\) on one line, where \(n\) is the initial number of apples and \(m\) is the number of events.

The second line contains \(n\) integers \(a_1, a_2, ..., a_n\) representing the initial value of each apple.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is a branch connecting apple \(u\) and apple \(v\).

The following \(m\) lines represent the events. Each event is in one of the following formats:

• 1 u v w
• 2 u w
• 3 u v w
• 4 u v w

It is guaranteed that for event type 1, the branch between \(u\) and \(v\) exists, and all events are given online.

outputFormat

For each event of type 4, output a single integer on a new line representing the number of premium apples (with value at least \(w\)) on the unique path between the given apples \(u\) and \(v\).

sample

3 4
1 2 3
1 2
2 3
4 1 3 2
3 1 2 1
4 1 3 2
2 2 -1

2
3