Дерево
Маленькая Аня любит рисовать. Сегодня в школе она услышала о графах и деревьях. Придя домой, она решила нарисовать дерево. Однако ей изображенные деревья не понравились. Тогда Аня взяла свои рисунки и покрасила все вершины дерева. Однако через некоторое время ей не понравилась раскраска, и она решила снова перекрасить вершины.
Аня считает, что районом вершины v радиуса k называется множество вершин, доступных из v на пути из не более k ребер. Дерево не ориентированное, по каждому ребру можно передвигаться в обоих направлениях. Иногда, когда она не занята очередным перекрашиванием вершин, Аня хочет узнать, сколько различных цветов присутствует в некотором районе. Но ей трудно ответить на такие вопросы, поэтому Аня просит Вас ей помочь.
Входные данные
Первая строка содержит три целых числа n, k и c (1 ≤ n ≤ 50000, 0 ≤ k ≤ 50, 1 ≤ c ≤ 50): количество вершин в дереве, максимальный радиус района, и количество разных цветов на палитре Ани (цвета пронумерованы от 1 до c). Вторая строка содержит n целых чисел c[i] (1 ≤ c[i] ≤ c), задающие цвета вершин изначально. Следующие n - 1 строка содержит описание дерева: i-ая из них содержит индексы вершин a[i] и b[i] (1 ≤ a[i], b[i] ≤ n), соединенных i-ым ребром. Гарантируется, что граф является деревом.
Следующая строка содержит количество q (1 ≤ q ≤ 10^5) запросов Ани. Следующие q строк содержат описание запросов в следующем формате. Первым идет d[i] (1 ≤ d[i] ≤ 2) - тип запроса.
если d[i] = 1, то далее следуют два целых числа v[i] и w[i] (1 ≤ v[i] ≤ n, 1 ≤ w[i] ≤ c): номер перекрашиваемой вершины и ее новый цвет.
если d[i] = 2, то далее следуют два целых числа v[i] и k[i] (1 ≤ v[i] ≤ n, 0 ≤ k[i] ≤ k): номер вершины - центра района и его радиус.
Выходные данные
Для каждого запроса второго типа вывести в отдельной строке количество различных цветов в заданном районе.