亚什喜欢玩树,当它们与素数有关时,他会特别兴奋。在他 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