Weakening the Tumorous Problems

In this problem, there is a tree with \(n\) nodes (numbered from \(1\) to \(n\)). Each node \(i\) is associated with a problem that has a tumor value \(a_i\). In order to hide his "toxic" problems, Little V places them on the nodes of the tree. A magic spell is cast on the tree so that anyone who wishes to explore the tree must perform a jump operation.

A jump operation is described by three integers \(s\), \(t\), and \(k\): starting at node \(s\) and aiming for node \(t\), the jumper travels along the unique simple path from \(s\) to \(t\). However, the movement is not continuous. Instead, the jumper makes multiple jumps along the path following these rules:

• If the number of edges from the current node to \(t\) is \(\le k\), the jumper directly jumps to \(t\).
• Otherwise, the jumper jumps exactly \(k\) edges forward along the path.

Let the simple path from \(s\) to \(t\) be \(P[0], P[1], \dots, P[L]\) where \(P[0]=s\) and \(P[L]=t\). The jumper always processes the starting node \(P[0]\), and then, after each jump, the landing node is processed. Therefore, the sequence of processed nodes is constructed as follows:

Set pos = 0, add P[pos]
while pos \( < L\):
    if (\(L - pos \le k\)) then pos = L
    else pos = pos + k
    add P[pos]

There are two types of jump operations:

1. Weakening Operation (op = 1): For each processed node \(i\) in the sequence, update \(a_i = \lfloor \sqrt{a_i} \rfloor\). No output is produced.
2. Statistical Operation (op = 2): Instead of weakening, calculate and output the sum of \(a_i\) values for each processed node in the sequence. In this case, the values \(a_i\) are not modified.

The operations are performed sequentially, and updates from weakening operations carry over to later operations. You are given the tree and a sequence of queries. For each statistical operation, output the corresponding sum.

inputFormat

The input is given as follows:

 n
 a1 a2 ... an
 u1 v1
 u2 v2
 ...
 un-1 vn-1
 q
 op1 s1 t1 k1
 op2 s2 t2 k2
 ...
 opq sq tq kq

Here, the first integer \(n\) is the number of nodes. The second line gives \(n\) integers \(a_1, a_2, \dots, a_n\). The next \(n-1\) lines each contain two integers \(u\) and \(v\) (an edge in the tree). Then an integer \(q\) is given—the number of queries. Each of the next \(q\) lines contains four integers. The first integer is the operation type (either 1 for a weakening operation or 2 for a statistical operation), followed by the starting node \(s\), the target node \(t\), and the step length \(k\).

outputFormat

For each query with operation type 2, output the sum of the tumor values along the processed nodes in the corresponding jump operation. Each answer should be on a separate line.

sample

5
16 9 4 25 36
1 2
1 3
3 4
3 5
4
2 2 4 1
1 5 4 2
2 2 4 1
2 5 4 1

54
34
15