D - Decorating Trees

Time limit: 5 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

You are given a tree with $n$ vertices numbered from $1$ to $n$ and rooted at vertex $1$. Initially, each vertex has a color $c_i$.


It is needed to perform $q$ queries of the following types:

  1. Update the colors of all vertices in the subtree of vertex $v$. For each vertex of the subtree replace its color by the formula: $c_i = (c_i + 1) \; mod \; 64$. Where $x \; mod \; y$ stands for the remainder that results of dividing $x$ by $y$.
  2.  Count the number of vertices in the subtree of vertex $v$ with color $c$.


Input

First line contains two integers $n$ and $q$ $(1 \leq n,q \leq 10^5)$, the number of vertices in the tree and the number of queries to perform.

Second line contains $n$ integers $c_i$ $(0 \le c_i \le 63)$, the initial colors of the vertices.

Next $n-1$ lines contain two integers $a$ and $b$ $(1\le a,b\le n)$ representing the edges of the tree.

Last $q$ lines contain the description of queries in the format described below:

           $1$ $v$ : Update the colors of all vertices in the subtree of vertex $v$ $(1 \le v \le n)$.

           $2$ $v$ $c$ : Count the number of vertices in the subtree of vertex $v$ $(1 \le v \le n)$ with color $c$ $(0 \le c\le 63)$.

Output

Print the solution for each query of type $2$. All solutions should be printed on a separate line following the same order given in the input.

Sample test(s)

Input
7 8 1 2 3 1 1 1 1 1 2 1 3 1 4 3 7 3 5 3 6 2 1 1 1 3 2 3 2 1 2 1 1 2 3 5 2 1 2 2 1 3
Output
5 3 1 2 3