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

Input	Output
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