Яш любит играть с деревьями, особенно если в этой игре замешаны простые числа. На его 20-й день рождения ему подарили корневое дерево, состоящее из n вершин, на котором он должен теперь отвечать на запросы. Услышав про деревья и простые числа, Яш так переполнился восхищением, что отвечать на запросы придётся теперь вам. Корнем дерева является вершина с номером 1. В каждой вершине записано некоторое целое число ai. Дополнительно нам дано целое число m.
Поступают запросы двух типов:
В первой строке входных данных записаны целые числа n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 1000) — количество вершин в дереве и значение m, используемое в запросах, соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 109) — изначальные значения, записанные в вершинах дерева.
Далее следует n - 1 строка, описывающая дерево. В каждой из них записаны два целых числа ui и vi (1 ≤ ui, vi ≤ n) — индексы вершин, соединённых i-м ребром.
В следующей строке записано число q (1 ≤ q ≤ 100 000) — количество запросов к дереву, которые требуется обработать.
В каждой из последних q строк записано 1 v x или 2 v (1 ≤ v ≤ n, 0 ≤ x ≤ 109), которые определяют запрос первого или второго типа соответственно. Гарантируется, что будет хотя бы один запрос второго типа.
Для каждого запроса второго типа выведите количество подходящих простых чисел.
8 20 3 7 9 8 4 11 7 3 1 2 1 3 3 4 4 5 4 6 4 7 5 8 4 2 1 1 1 1 2 5 2 4
3 1 1
5 10 8 7 5 1 0 1 2 2 3 1 5 2 4 3 1 1 0 1 1 2 2 2
2
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач