K. Chocolate Tree
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Valentine's Day has come, and Bob prepared the perfect gift for his girlfriend, Alice. The gift is a rooted tree of chocolates where each chocolate has a type. To make the day more interesting, he decided to play a game with his girlfriend using the gift. The game lasts for $$$q$$$ operations, where the operation is one of the following:

  • $$$1$$$ $$$u$$$ $$$v$$$ $$$k$$$ : Alice has to tell Bob how many chocolates of type $$$k$$$ exist on the simple path from $$$u$$$ to $$$v$$$.
  • 2 $$$u$$$ $$$k$$$ : Bob gives the chocolate in node $$$u$$$ to Alice to eat and replaces it with chocolate of type $$$k$$$.

You have to help Alice answer the first type of operations.

The root of the tree is node $$$1$$$.

Tree: A connected acyclic undirected graph where there is only $$$1$$$ simple path between any $$$2$$$ pairs of nodes.

Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q \leq 2.10^{5})$$$

The second line contains $$$n$$$ integers $$$t_{i}$$$ $$$(1\leq t_{i} \leq 10^{6})$$$, the type of the chocolate in node $$$i$$$.

The next $$$n-1$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n)$$$, which means there is an edge between node $$$u$$$ and node $$$v$$$.

The next $$$q$$$ lines contain one of $$$2$$$ operations:

  • $$$1$$$ $$$u$$$ $$$v$$$ $$$k$$$ $$$(1 \leq u,v\leq n, 1\leq k \leq 10^{6})$$$
  • $$$2$$$ $$$u$$$ $$$k$$$ $$$(1 \leq u\leq n, 1\leq k \leq 10^{6})$$$
Output

Print the answer for the operations of type 1 in separate lines.

Example
Input
9 9
1 2 3 4 5 6 7 8 9
1 2
2 3
3 4
4 5
2 6
2 7
6 8
4 9
1 5 9 2
1 5 9 4
1 5 9 5
1 5 9 6
1 5 7 6
1 5 7 3
1 5 7 8
2 3 6
1 5 7 6
Output
0
1
1
0
0
1
0
1