Яш любит играть с деревьями, особенно если в этой игре замешаны простые числа. На его 20-й день рождения ему подарили корневое дерево, состоящее из n вершин, на котором он должен теперь отвечать на запросы. Услышав про деревья и простые числа, Яш так переполнился восхищением, что отвечать на запросы придётся теперь вам. Корнем дерева является вершина с номером 1. В каждой вершине записано некоторое целое число ai. Дополнительно нам дано целое число m.
Поступают запросы двух типов:
- Для данной вершины v и целого числа x — увеличить все ai в поддереве v на x.
- Для данной вершины v — найти количество таких простых чисел p, меньших m, что найдётся вершина u в поддереве вершины v и целое число k, такие что au = p + m·k.
Выходные данные
Для каждого запроса второго типа выведите количество подходящих простых чисел.
Примеры
| № | Входные данные | Выходные данные |
|
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
|