Tree Rainbow Queries

Given a tree with n nodes numbered from 1 to n and an integer sequence \(\{z_1,z_2,\cdots,z_n\}\), all nodes initially have weight 0. You are also given q commands, each of one of the following two types:

• Type 1: 1 l r. Let \(S_0\) be the minimal rainbow of the interval \([l,r]\). A vertex set \(S\) is said to be connected if for every two vertices \(u,v \in S\) every vertex on the unique simple path between \(u\) and \(v\) is also in \(S\). The set \(S\) is a rainbow for \([l,r]\) if it is connected and contains every vertex in \([l,r]\). The minimal rainbow \(S_0\) is the unique rainbow with the smallest size. For this command, for each vertex \(u \in S_0\), increase its weight \(w_u\) by 1.
• Type 2: 2 l r u. Compute \[ \left( \sum_{i=l}^{r} 19901991^{\;z_{\gcd(i,u)} \cdot w_i} \right) \bmod 20242024. \]</p>

The tree is given by its n-1 edges. It is guaranteed that the tree is connected. The indices used in the sequence \(z\) and in the commands are 1-indexed.

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 105).

The next n-1 lines each contain two integers u and v representing an edge in the tree.

The next line contains n integers: z1, z2, \(\ldots\), zn.

The following q lines each describe a command in one of the following formats:

• 1 l r
• 2 l r u

outputFormat

For each command of type 2, output one line containing the required result.

sample

3 3
1 2
2 3
1 1 1
1 1 3
2 2 3 2
2 1 1 3

19561958
19901991