eolymp
bolt
Try our new interface for solving problems

Tree

Time limit 1 second
Memory limit 512 MiB

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 data

The first line contains three integers n, k and c (1n50000, 0k50, 1c50): 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] (1c[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] (1a[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 (1q10^5) of Annie's queries. The following q lines contain the description of queries in the following format. The first integer d[i] (1d[i]2) is the type of query.

If d[i] = 1, it is followed by two integers v[i] and w[i] (1v[i]n, 1w[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] (1v[i]n, 0k[i]k): the number of the center node of a district and its radius.

Output data

For each query of the second type, print the number of different colors in the given district on a separate line.

Examples

Input example #1
5 2 3
2 1 1 3 2
1 2
1 3
1 4
4 5
6
2 4 1
2 1 1
1 4 1
2 1 1
1 1 1
2 1 1
Output example #1
2
3
2
1
Source 2013 Petrozavodsk, Moscow SU ST + NNSU Contest, Day 2, August 24, Problem D