← 返回题目列表

Codeforces · 633/G

G. 亚什和树

中文机器翻译题面 查看原题

亚什喜欢玩树,当它们与素数有关时,他会特别兴奋。在他 20 岁生日那天,他被授予一棵有 n 个节点的有根树来回答查询。听到树上的素数,亚什兴奋得陶醉了,并请你帮忙并回答他关于树的疑问。树以节点 1 为根。每个节点 i 都有一些与其关联的值 ai。另外,给出整数m。

有两种类型的查询:

1.对于给定的节点v和整数值x,将节点v的子树中的所有ai增加值x
2. 对于给定的节点 v,找到小于 m 的素数 p 的个数,其中 v 的子树中存在节点 u 且非负整数值 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

输出 #1

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

2