Background

$\text{TYM}$ is an agent.
The country where $\text{TYM}$ lives is being invaded, and he is given a mission: to deliver information between cities.

Problem Description

The country where $\text{TYM}$ lives has $n$ cities, numbered $1,\dots,n$, connected by $n - 1$ bidirectional roads. It is guaranteed that there is a unique simple path between any two cities.
Also, each city has an information flow rate $a_i$.

$\text{TYM}$ needs to perform a total of $m_0$ missions. Each mission gives two cities $s,t$, and is carried out as follows:
At the first moment, he starts from city $s$ and moves along the simple path between $s$ and $t$ to reach $t$, moving to the next city in each time unit.
Every time he arrives at a city, he sends that city’s information flow $a_i$ to every city on the route he passes through.
We agree that at the same moment he arrives at a city, he also sends that city’s information flow to itself. We define the value of a city as the product of all information flows received by that city.

For each mission, compute the sum of the values of the cities on the simple path from $s$ to $t$, modulo $20924$.

In addition, unfortunately, because the invaders are also acting at the same time, between his missions, some $a_i$ may change.

The total number of missions plus the number of times an $a_i$ is changed is $m$.

Input Format

The first line contains two integers $n,m$.
The second line contains $n$ integers; the $i$-th integer represents the information flow rate $a_i$ of city $i$.
The next $n - 1$ lines each contain two integers $u,v$, indicating that there is a bidirectional road between $u$ and $v$.
The next $m$ lines each describe a mission or an update event:

• In the form Q s t, meaning $\text{TYM}$ performs a mission from $s$ to $t$.
• In the form C x k, meaning the invaders’ action makes $a_x \rightarrow a_x + k$.

Output Format

For each mission, output the total sum of information flow received by the cities on the route.

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

Hint

Constraints:

For $20\%$ of the testdata, $1 \leq n,m \leq 2000$.
For an additional $20\%$ of the testdata, $a_i=2$, and there are no update operations.
For an additional $20\%$ of the testdata, the roads connect $i$ to $i+1$.
For $100\%$ of the testdata, $1 \leq n,m \leq 10^5, 1 \leq a_i \leq 20923$.

Sample Explanation:

For the first query, $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$.
Update: $a_1 = 1 + 2 = 3$.
For the second query, $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$.

Translated by ChatGPT 5