Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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)