Description

$\hspace{15px}$大家都说小憨出的树学家II太简单了，小憨一怒之下当场就出了这一道题：
$\hspace{15px}$小憨拿到了一棵由 $n$ 个节点，节点编号从 $1$ 到 $n$ 构成的以 $1$ 为根节点的有根树，每个节点都有一个位运算符 $op_i$ 和权值 $a_i$。一个数值 $val$ 经过节点 $i$ 时会被替换为其位运算符和权值进行运算后的结果，更形式化地讲：$val \larr val \space op_i \space a_i$。
$\hspace{15px}$现在小憨共有 $q$ 次操作：

• 操作 1：将节点 $x$ 的操作符修改为 $op$，权值修改为 $val$。
• 操作 2：查询数值 $val$ 从节点 $x$ 开始，持续运算到节点 $y$ 的结果。

$\hspace{15px}$树是指这样的一张图，其由 $n$ 个节点和 $n-1$ 条边构成，其上的任意两个点都连通，且不存在环。

Format

Input

$\hspace{15px}$第一行输入两个整数 $n,q \space (1 \leq n, q \leq 1e5)$ 表示节点的数量和操作次数。
$\hspace{15px}$第二行有 $n$ 个位运算操作符 $op$ ，$op_i$ 表示第 $i$ 个节点的操作符。$( op_i \in \{ \& , \mid \space, \widehat\space \}$$)$
$\hspace{15px}$第三行有 $n$ 个非负整数 $a_i \space (0 \leq a_i < 2^{31})$ 表示节点 $i$ 的权值。
$\hspace{15px}$此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leq u_i, v_i \leq n;\ u_i \neq v_i)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证树连通。
$\hspace{15px}$此后 $q$ 行，第 $i$ 行输入的第一个整数为操作类型，若为操作 $1$ ,后续输入为 $x, op, val \space ;$若为操作 $2$ ,后续输入为 $val, x, y$。

Output

$\hspace{15px}$对于每个操作 $2$， 输出一行一个整数表示查询的答案。

Samples

5 3
| | & ^ |
10 10 10 5 10
1 3
1 2
2 4
2 5
2 0 5 3
1 1 & 8
2 0 5 3

10
8