Dungeon Damage Accumulation

In the ac world dungeons there are n small rooms connected by exactly n-1 corridors forming a tree. Each room i spawns a monster whose damage is a_i. In every corridor a one‐way door is installed. Every second, one of the following events occurs:

1. A monster is generated in room x. The monster will never cross walls; it only moves in the direction permitted by the one‐way doors.
2. The monster generated in room x is killed by ac's servant.
3. ac, who wishes to AFK his damage farming, ponders the following: if he had been standing in room x continuously from time 1 to the current time, what is the maximum damage he could have received at any moment? Damage at a moment is defined as the total of damage values of all monsters that can reach ac’s room (i.e. there is a directed path from the monster's room to ac's room through the one-way doors).

Simplified Problem Statement:

You are given a tree with n nodes. Each node has a weight a_i and each of the n-1 edges has an assigned direction. There is a dynamic set (initially empty) on which you will perform the following operations:

1. Add a node to the set.
2. Remove a node from the set.
3. Given a node x, let the current damage at room x be the sum of the weights a_u for all nodes u in the set such that there is a directed path from u to x (i.e. u \to x in the directed tree). Query the maximum historical value of this damage from time 1 to the current moment.

Note: A directed path from u to x means that if the unique simple path from u to x is u=v₀, v₁, ..., v_k=x, then for every i (0 ≤ i < k) the edge between v_i and v_i+1 must be oriented from v_i to v_i+1 (i.e. in v_i \to v_i+1 direction). The room where ac stands does not affect monster generation or killing events.

inputFormat

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

The second line contains n integers: a1, a2, ..., an, where ai is the damage value of the monster generated in room i.

The next n-1 lines each contain two integers u and v indicating there is a directed edge from u to v (i.e. the one‐way door allows movement from room u to room v).

The next q lines each describe an operation in one of the following formats:

• 1 x : Add room x to the set (a monster is spawned in room x).
• 2 x : Remove room x from the set (the monster from room x is killed). It is guaranteed that room x is present in the set when this operation is performed.
• 3 x : Query the maximum historical damage at room x from time 1 until now. Damage at a moment is computed as the sum of a[u] for all rooms u currently in the set such that there is a directed path from u to x.

outputFormat

For each query operation (operation type 3), output one line containing a single integer: the maximum historical damage at the queried room.

sample

3 5
5 3 2
1 2
3 2
1 1
1 3
3 2
2 1
3 2

7
7