Дерево
Маленька Аня любить малювати. Сьогодні в школі вона дізналася про графи та дерева. Повернувшись додому, вона вирішила намалювати дерево. Однак їй не сподобалися намальовані дерева. Тоді Аня взяла свої малюнки і пофарбувала всі вершини дерева. Але згодом їй не сподобалося фарбування, і вона вирішила перефарбувати вершини знову.
Аня вважає, що районом вершини 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): номер вершини - центру району і його радіус.
Вихідні дані
Для кожного запиту другого типу виведіть в окремому рядку кількість різних кольорів у заданому районі.