Problem Description

You are given a tree with $n$ nodes.

• A set of nodes $S$ is called connected if and only if for all $u, v \in S$, every node on the simple path from $u$ to $v$ is also in $S$.
• A set of nodes $S$ is called a rainbow of $[l, r]$ if and only if $S$ is connected and $S$ contains all nodes in $[l, r]$.
• A set of nodes $S_0$ is called the minimum rainbow of $[l, r]$ if and only if $S_0$ has the smallest size among all rainbows of $[l, r]$. It can be proven that $S_0$ is unique.

Each node has a weight. The weight of node $u$ is $w_u$. Initially, all node weights are $0$. Also, you are given a sequence $\{z_1, z_2, \cdots, z_n\}$.

You are given $q$ commands. Each command is one of the following two types:

• 1 l r: Let $S_0$ be the minimum rainbow of $[l, r]$. For all $u \in S_0$, increase $w_u$ by $1$.
• 2 l r u: Compute $\left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024}$.

Input Format

The first line contains two positive integers $n, q$.

The second line contains $n$ non-negative integers, representing $z_1, z_2, \cdots, z_n$ in order.

The next $n - 1$ lines each contain two positive integers $u, v$, describing an edge in the tree between $u$ and $v$.

The last $q$ lines each contain $3$ or $4$ positive integers, describing a command.

Note: Each line in the input file ends with \r. Please filter it out by yourself.

Output Format

For each query (i.e. each command of the second type), output the answer.

5 4
1 0 0 0 1
1 2
1 3
3 4
3 5
1 2 3
2 1 3 3
1 4 5
2 3 5 3

19561959
19561959

Hint

This problem uses bundled testdata.

For all testdata, it is guaranteed that: $1 \le n, q \le 8 \times 10^4, 0 \le z_i \le 10^9$. All commands satisfy $1 \le l \le r \le n, 1 \le u \le n$. It is guaranteed that $(l, r)$ in the first type of commands are generated randomly. The random generation method is as follows:

• Randomly generate $l$ uniformly in $[1, n] \cap \mathrm{Z}$.
• Randomly generate $r$ uniformly in $[1, n] \cap \mathrm{Z}$.
• If $l > r$, swap $l$ and $r$.

Constraints

Special Property A: It is guaranteed that all commands of the second type appear after all commands of the first type.

Special Property B: It is guaranteed that the number of commands of the second type is $\le 20$.

Translated by ChatGPT 5