TYM's Information Flow

A country has n cities numbered from 1 to n connected by n-1 bidirectional roads forming a tree (i.e. there is a unique simple path between any two cities). Each city i has an information flow value a_i.

TYM needs to execute several operations (queries and updates). Initially, there are two types of operations:

• Query operation: Given two cities s and t, TYM travels along the unique simple path from s to t. He starts at s at time 1 and at each subsequent time moves to the next city along the path. When he arrives at a city, he sends that city’s current information flow value to every city he has visited so far including the city he just arrived at. For a city on the path, define its value as the product of all information flow values it has received. In particular, if the path is [v₁, v₂, ..., v_k] (with v₁ = s and v_k = t), then:</p>

  value(v₁) = a_v1 * a_v2 * ... * a_vk

  value(v₂) = a_v2 * a_v3 * ... * a_vk

  ...

  value(v_k) = a_vk

  Your task for a query operation is to compute the sum of the values of all cities on the simple path from s to t, modulo 20924. That is, output

  [ \sum_{i=1}^{k} \left( \prod_{j=i}^{k} a_{v_j} \right) \mod 20924. ]

  Update operation: In the meantime, due to adversaries’ actions, the information flow of some city may change between operations. In an update operation, you are given a city index i and a new value x, and you must update a_i to x.

  The total number of operations (queries plus updates) is m.

  Input/Output Format: See the descriptions below.

  inputFormat

  The first line contains two integers n and m — the number of cities and the total number of operations.

  The second line contains n integers: a₁, a₂, ..., a_n, where a_i is the information flow of city i.

  The next n-1 lines each contain two integers u and v indicating that there is a bidirectional road connecting cities u and v.

  The following m lines each describe an operation. Each operation is in one of the following two formats:

  • Q s t — a query operation asking for the sum of values on the simple path from city s to city t.
  • C i x — an update operation which changes the information flow of city i to x.

  It is guaranteed that the given roads form a tree.

  outputFormat

  For each query operation, output a single line containing the required sum modulo 20924.

  sample

  5 5
  2 3 5 7 11
  1 2
  2 3
  2 4
  4 5
  Q 1 5
  C 2 4
  Q 1 5
  C 5 1
  Q 3 5

  781
  1012
  176

  </p>