思路

• 关键性质：对于权值集合的最小公倍数，若把每个数按素数分解 $w=\prod p^{e_p}$，则 LCM 对应每个素数的指数取最大值。由于 $w_i \le 100$，素数仅有 $25$ 个（不超过 $97$），各指数极小（如 $2$ 的最大指数为 $6$）。

• 路径查询：仅为根到 $x$ 的路径。用重链剖分将路径拆成 $O(\log n)$ 个链段。

• 数据结构：用一棵线段树，节点维护一个长度为 $25$ 的小数组，表示该区间所有黑色节点对每个素数的指数最大值（白色为全零）。

  • 翻转颜色 → 点更新（设为该点的指数向量或全零）。
  • 查询根到 $x$ → 若干区间查询，合并（逐素数取最大），最后计算

题目内容

给定一棵以节点 $1$ 为根的有 $n$ 个节点的树，每个节点 $i$ 有一个正整数权值 $w_i$ ，初始被涂成黑色或白色。你需要支持以下两种操作；

1.翻转节点 $x$ 的颜色(黑色变白色，自色变黑色)；

2.查询从根节点 $1$ 到节点 $x$ 的路径上所有黑色节点的权值的最小公倍数(若路径上无黑色节点，则记为 $1$ )

【名词解释】

最小公倍数：最小公倍数是能够被给定整数集合中每个整数整除的最小正整数，记为 $Lcm$ 。

输入描述

第一行输入两个整数 $n$ 和 $q(1≦n,q≦2×10^5)$，分别表示树的节点数量和操作数量。

第二行输入 $n$ 个整数 $w_1,w_2,...,w_n(1≦w_i≦100)$，分别表示节点 $1$ 到节点 $n$ 的权值。

第三行输入一个长度为 $n$ 、仅由字符 $B$ 和 $W$ 构成的字符串 $c$，其中 $c_1=B$ 表示节点 $i$ 初始化为黑色，$c_i=W$ 表示初始化为白色。

接下来 $n-1$ 行，每行输入两个整数 $u_i$ 和 $v_i(1≦u_i,v_i≦n;u_i≠v_i)$ ，表示一条连接节点 $u_i$ 和节点 $v_i$ 的无向边，保证这 $n$ 个节点构成一颗根为 $1$ 的树。

接下来 $q$ 行，每行输入两个整数 $t$ 和 $x(t∈{1,2},1≦x≦n)$ ，表示一次操作。

1.当 $t=1$ 时，执行翻转操作；

2.当 $t=2$ 时，执行查询操作。

输出描述

对于每次查询操作，在一行中输出一个整数，表示对应路径上黑色节点权值的最小公倍数对 $(10^9+7)$ 取模后的结果。

样例1

输入

5 5
2 3 4 5 6
BWBWB
1 2
1 3
3 4
3 5
2 4
1 3
2 4
1 1
2 5

输出

4
2
6

说明

在这个样例中，初始颜色为

• 节点 $1→B$ ；

• 节点 $2→W$ ；

• 节点 $3→B$ ；

• 节点 $4→W$ ；

• 节点 $5→B$ 。

第一条查询 $2$ $4$ ：路径 $1-3-4$ 上黑色节点为 $1,3$ ，权值分别为 $2,4$ ，$lcm(2,4)=4$，翻转节点 $3$ 后第二次查询 $2$ $4$ ；路径上仅剩节点 $1$ 为黑色，$lcm(2)=2$ ，再翻转节点 $1$ 后第三次查询 $2$ $5$ ；路径 $1-3-5$ 上仅有节点 $5$ 为黑色，$lcm(6)=6$ 。