Ada the Ladybug has many friends who live on a tree. Each of them is fan of a football team. Ada sometime go on a trip from one friend to another. If she meets a friend she tells him/her about all previously visited friends who are fans of the same team. The visited friend will gain **+1** happiness for each friend Ada told him/her about.

Ada is wondering (for each trip) what will be the total gaines happiness.

Also note that sometime a friend changes his/her mind and start to support different team.

### Input

The first line two integers **1 ≤ N Q ≤ 105** , the number of friends ( **N** ) and the number of queries.

The next line will contain **N** integers **0≤ Ai ≤ 105** , the team which **ith** friend supports.

The next **N-1** lines will contain two integers **0 ≤ a, b < N** , the friends which will be connected by a branch (edge).

The next **Q** lines will be of two kinds:

**1 x y** ( **0 ≤ x < N** , **0 ≤ y ≤ 105** ), meaning that **xth** friend will start supporting team **y** (instead of the old one).

**2 a b** ( **0 ≤ a, b < N** ), meaning that Ada will travel from friend **a** to friend **b** and wants to know the happiness.

### Output

For each query of second kind, output the gained happiness.