Маленькая Аня любит рисовать. Сегодня в школе она услышала о графах и деревьях. Придя домой, она решила нарисовать дерево. Однако ей изображенные деревья не понравились. Тогда Аня взяла свои рисунки и покрасила все вершины дерева. Однако через некоторое время ей не понравилась раскраска, и она решила снова перекрасить вершины.

Аня считает, что районом вершины v радиуса k называется множество вершин, доступных из v на пути из не более k ребер. Дерево не ориентированное, по каждому ребру можно передвигаться в обоих направлениях. Иногда, когда она не занята очередным перекрашиванием вершин, Аня хочет узнать, сколько различных цветов присутствует в некотором районе. Но ей трудно ответить на такие вопросы, поэтому Аня просит Вас ей помочь.

Входные данные

Первая строка содержит три целых числа n, k и c (1 ≤ n ≤ 50000, 0 ≤ k ≤ 50, 1 ≤ c ≤ 50): количество вершин в дереве, максимальный радиус района, и количество разных цветов на палитре Ани (цвета пронумерованы от 1 до c). Вторая строка содержит n целых чисел ci (1 ≤ ci ≤ c), задающие цвета вершин изначально. Следующие n - 1 строка содержит описание дерева: i-ая из них содержит индексы вершин ai и bi (1 ≤ ai, bi ≤ n), соединенных i-ым ребром. Гарантируется, что граф является деревом.

Следующая строка содержит количество q (1 ≤ q ≤ 105) запросов Ани. Следующие q строк содержат описание запросов в следующем формате. Первым идет di (1 ≤ di ≤ 2) - тип запроса.

если di = 1, то далее следуют два целых числа vi и wi (1 ≤ vi ≤ n, 1 ≤ wi ≤ c): номер перекрашиваемой вершины и ее новый цвет.

если di = 2, то далее следуют два целых числа vi и ki (1 ≤ vi ≤ n, 0 ≤ ki ≤ k): номер вершины - центра района и его радиус.

Выходные данные

Для каждого запроса второго типа вывести в отдельной строке количество различных цветов в заданном районе.