Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

G. Яш и деревья
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яш любит играть с деревьями, особенно если в этой игре замешаны простые числа. На его 20-й день рождения ему подарили корневое дерево, состоящее из n вершин, на котором он должен теперь отвечать на запросы. Услышав про деревья и простые числа, Яш так переполнился восхищением, что отвечать на запросы придётся теперь вам. Корнем дерева является вершина с номером 1. В каждой вершине записано некоторое целое число ai. Дополнительно нам дано целое число m.

Поступают запросы двух типов:

  1. Для данной вершины v и целого числа x — увеличить все ai в поддереве v на x.
  2. Для данной вершины v — найти количество таких простых чисел p, меньших m, что найдётся вершина u в поддереве вершины v и целое число k, такие что au = p + m·k.
Входные данные

В первой строке входных данных записаны целые числа 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