New Year Tree

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Each vertex of a rooted tree has a color from 1 to 60. Support recoloring every vertex in a subtree with one color and querying the number of distinct colors in a subtree.

Input

The first line contains $n$ and $m$. The second line contains the $n$ initial colors. The next $n-1$ lines contain the tree edges. Each of the following $m$ lines is one of:

• 1 v c: recolor every vertex in the subtree of $v$ with color $c$.
• 2 v: query the number of distinct colors in the subtree of $v$.

The tree is rooted at vertex 1.

Output

For each operation of type 2, print the number of distinct colors.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,m\le4\cdot10^5$.
• $1\le c_i,c\le60$.

Example

Input

1 15
43
2 1
2 1
2 1
2 1
2 1
1 1 13
2 1
2 1
2 1
2 1
2 1
1 1 34
2 1
2 1
2 1

Output

1
1
1
1
1
1
1
1
1
1
1
1
1

Explanation

The tree contains only one vertex, so every query reports exactly one distinct color.