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 ≤ 10⁵, the number of friends (N) and the number of queries.

The next line will contain N integers 0≤ A_i ≤ 10⁵, the team which i^th 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 ≤ 10⁵), meaning that x^th 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.

Example Input

7 8
0 0 1 2 1 1 2
0 1
1 5
1 2
2 4
2 3
3 6
2 4 5
2 0 6
2 1 3
1 1 2
1 2 2
2 4 5
2 0 6
2 1 3

Example Output

3
2
0
2
6
3