Yet Another Xinversion

The problem statement is simple. You are given a rooted tree (1 is the root) and every node has a cost, say $C_i$. You have to perform $Q$ operations. Each operation can be one of the following types.

• Given $u$, $val$. you have to set $C_u = val$.
• Given $u$. You have to find the Xinversion of $u$.

Xinversion is almost similar to the inversion of an array. Xinversion of a node $x$ is the number of nodes $y$ inside the subtree of $x$ such that $C_y > C_x$.

Input

In the first line you are given two integers $N$ ($1 \leq N \leq 10^5$) and $Q$ ($1 \leq Q \leq 10^5$), the number of nodes and the number of operations respectively.

The next line will contain $N$ integers, $i$-th integer represents $C_i$ ($1 \leq C_i \leq 10^9$).

Each of the next $N-1$ lines will contain two integers $u$, $v$ which means $u$ and $v$ are connected with an edge.

Each of the next $Q$ lines will contain one of the two types of operations:

• 1 u val
• 2 u

Output

For every operations of type 2, print the Xinversion of $u$.

Sample

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

4
3
2