Олимпиадный тренинг

Задача . G. Яш и деревья


Яш любит играть с деревьями, особенно если в этой игре замешаны простые числа. На его 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), которые определяют запрос первого или второго типа соответственно. Гарантируется, что будет хотя бы один запрос второго типа.

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

Для каждого запроса второго типа выведите количество подходящих простых чисел.


Примеры
№Входные данныеВыходные данные
1
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
2
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
Статистика успешных решений по компиляторам
 Кол-во
С++5