Given a tree with $n$ nodes.

• A set of nodes $S$ is called connected if and only if for all $u, v \in S$, all nodes on the simple path between $u$ and $v$ are 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 minimal rainbow of $[l, r]$ if and only if $S_0$ is the smallest among all rainbows of $[l, r]$. It can be proven that $S_0$ is unique.

Each node has a weight $w_u$, and initially, all weights are $0$. Additionally, a sequence $\{z_1, z_2, \cdots, z_n\}$ is given.

Given $q$ commands, each command is one of the following two types:

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

Input

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 between $u$ and $v$ in the tree.

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

Output

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

Examples

Input 1

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

Output 1

19561959
19561959

Constraints

This problem uses bundled testing.

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

• Generate $l$ uniformly at random in $[1, n] \cap \mathbb{Z}$.
• Generate $r$ uniformly at random in $[1, n] \cap \mathbb{Z}$.
• If $l > r$, swap $l$ and $r$.

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

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