Tree
Little Annie loves drawing. Today at school she heard about graphs and trees. Upon arriving home, she decided to draw a tree. But it seemed to her that her tree is not beautiful. Then Annie took her paints, and colored all the nodes of a tree. But after some time, she got tired of this coloring, so she decided to repaint the nodes.
Annie says that a district of node v with radius k is a set of nodes which are accessible from the node v by moving along at most k edges. The tree is not directed, so each edge can be traversed in both directions. Sometimes when not busy repainting the nodes, she wonders how many different colors there are in some district. But it is very difficult for her to answer these questions, so Annie asks you to help her.
Input
The first line contains three integers n, k and c (1 ≤ n ≤ 50000, 0 ≤ k ≤ 50, 1 ≤ c ≤ 50): the number of nodes in the tree, the maximum radius of the district, and the number of different colors in Annie's palette (the colors are numbered from 1 to c). The second line contains n integers c[i] (1 ≤ c[i] ≤ c) describing the colors in which the nodes were originally painted. The following n - 1 lines contain the description of the tree: i-th of them contains two integers a[i] and b[i] (1 ≤ a[i], b[i] ≤ n), indices of vertices joined by i-th edge. It is guaranteed that the given graph is a tree.
The next line contains the number q (1 ≤ q ≤ 10^5) of Annie's queries. The following q lines contain the description of queries in the following format. The first integer d[i] (1 ≤ d[i] ≤ 2) is the type of query.
If d[i] = 1, it is followed by two integers v[i] and w[i] (1 ≤ v[i] ≤ n, 1 ≤ w[i] ≤ c): the number of a node being recolored and its new color.
If d[i] = 2, it is followed by two integers v[i] and k[i] (1 ≤ v[i] ≤ n, 0 ≤ k[i] ≤ k): the number of the center node of a district and its radius.
Output
For each query of the second type, print the number of different colors in the given district on a separate line.