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$. For more clear idea, see the sample input-output section.