A. Xcellent Tree Query Problem

Problem Description

Given a tree consisting of $n$ nodes. Each node initially have a color $c_i$. You are given $m$ commands, each of them is one of the follows:

• $1\ x$: Cut the $x$-th edge of the input.
• $2\ x\ l\ r\ v$: For every $y$ currently connected with $x$ (that is, no edges lying on the simple path from $x$ to $y$ is cut), if $l\le c_y\le r$, set $c_y$ to $v$.
• $3\ x\ l\ r$: Count the number of $y$ currently connected with $x$, that satisfy $l\le c_y\le r$.

Input

The first line of the input contains two integers $n$ ($1\leq n\leq 10^5$) and $m$ ($1\leq m\leq 5\times 10^5$). The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1\leq c_i\leq n$). Each of the following $n - 1$ lines contains two integers $u, v$ ($1 \le u, v \le n$, $u \ne v$) - an edge of the tree. Each of the following $m$ lines contains one of the three commands listed above. It's guaranteed that no edges is cut twice or more. It's also guaranteed that in command of type $2$ and $3$, $1\le l\le r\le n$, $1\le x, v\le n$.

Output

For every command of type $3$, output the answer in a single line.

Sample Input

10 19
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 4
4 5
4 6
5 7
5 8
1 9
9 10
3 4 1 10
3 8 3 4
2 9 9 10 1
3 4 1 10
3 2 8 10
1 4
3 8 1 10
3 7 7 8
2 5 5 7 9
3 7 9 10
2 1 1 2 3
3 1 3 3
1 1
3 1 3 3
2 10 3 9 4
3 1 4 4
2 3 3 5 9
3 3 6 10
3 3 6 6

Sample Output

10
2
10
1
3
2
2
5
3
3
4
1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）