题目背景

$\text{TYM}$ 是一名特工。
$\text{TYM}$ 所在的国家正受到侵犯，他被赋予一个任务：于城市之间传递信息。

题目描述

$\text{TYM}$ 所在的国家有 $n$ 个城市，编号为 $1,\dots,n$，由 $n - 1$ 条双向道路连接。保证任意两个城市间都有唯一的简单路径。
以及，每个城市都有一个信息流的流量 $a_i$。

$\text{TYM}$ 一共要执行 $m_0$ 个任务，每个任务给定两个城市 $s,t$，其执行过程如下：
第一个时刻，他从城市 $s$ 出发，以每个时刻移动到下一个城市的速度，走 $s,t$ 之间的简单路径到 $t$。
每到达一个城市，他都会把这个城市的信息流 $a_i$ 发送到经过的每个城市。
我们约定，他到达一个城市的同一时刻也会把这个城市的信息流发送给这个城市。我们定义一个城市的价值为这个城市所接受到的信息流的乘积。

请你求出每个任务中，$s$ 到 $t$ 的简单路径上经过的城市的价值的总和对 $20924$ 取模的结果。

此外，不幸地，由于侵略者同时也在行动，所以在他执行多个任务之间，可能会有某个 $a_i$ 发生改变。

他的任务总数与改变某个 $a_i$ 的次数之和为 $m$。

输入格式

第一行，两个整数 $n,m$。
第二行，$n$ 个整数，第 $i$ 个表示第 $i$ 个城市的信息流流量 $a_i$。
以下 $n - 1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条双向道路。
以下 $m$ 行，每行描述一个任务或是一次修改事件：

• 形如 Q s t，表示 $\text{TYM}$ 从 $s$ 到 $t$ 执行了一次任务。
• 形如 C x k，表示侵略者的行动令 $a_x \rightarrow a_x + k$。

输出格式

对于每次任务，输出经过的城市收到的信息流总流量。

5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
Q 1 5
C 1 2
Q 1 5

325
565

提示

数据范围：

对于 $20\%$ 的数据，$1 \leq n,m \leq 2000$；
对于额外的 $20\%$ 的数据，满足 $a_i=2$，且没有修改操作；
对于额外的 $20\%$ 的数据，满足道路从 $i$ 连向 $i+1$；
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^5,1 \leq a_i \leq 20923$。

样例解释：

第一个询问，$1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 325$；
修改，$a_1 = 1 + 2 = 3$；
第二个询问，$3 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 565$；