Not long ago, Xiao V was a Tsinghua training camp contestant, sitting in the computer lab struggling with his fading OI career. Now, he has become a glorious problem setter. He felt very excited and couldn't help but exclaim: "Hello world!".

Xiao V has $n$ problems, and his problems are all very "toxic," so ufozgg, who cares about the contestants, intends to weaken these problems. To avoid being weakened, Xiao V hid his toxic problems in a tree with $n$ nodes (nodes are numbered from $1$ to $n$), where all nodes in the tree correspond one-to-one with Xiao V's problems. Each of Xiao V's problems has a "toxicity value," and the toxicity value of the problem corresponding to node $i$ (the node labeled $i$ in the tree, same below) is $a_i$.

To protect his problems, the magician Xiao V cast a spell on the tree. As a result, anyone who wants to explore the tree must perform jump operations on it. Each jump operation consists of a starting point $s$, an ending point $t$, and a step frequency $k$. This means the jumper starts from $s$ and reaches $t$ by jumping multiple times along the simple path on the tree. For each jump, if the length of the shortest path from the current point to $t$ is no more than $k$, the jumper will jump directly to $t$; otherwise, the jumper will jump exactly $k$ edges along the shortest path.

Since Xiao V hid the problems in the tree, ufozgg cannot weaken the problems directly. He must jump on the tree and weaken the problems while jumping. Every time ufozgg passes through a node during a jump (including the starting point $s$, even when $s=t$), he will take the square root of the toxicity value of the problem at that node and round it down: that is, if he passes through node $i$, he will set $a_i = \lfloor{\sqrt{a_i}}\rfloor$. We call this operation a "weakening operation."

ufozgg also wants to know the extent of his weakening of the problems from time to time. Therefore, in some jump operations, he will forgo weakening the problems and instead calculate the sum of the toxicity values of the problems at the nodes passed during that jump. We call this operation a "statistical operation."

The bystander Lv Lv is very interested in Xiao V's toxic problems and ufozgg's weakening plan. He now wants to know the result obtained by ufozgg each time he performs a statistical operation. Can you help him?

Input

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The next line contains $n$ space-separated positive integers $a_1, a_2, \dots, a_n$, describing the toxicity values of the problems at each node in order.

The next $n-1$ lines describe the tree. Each line contains $2$ positive integers $u, v$, describing an edge $(u, v)$ in the tree. (It is guaranteed that $1 \leq u, v \leq n$ and that these $n-1$ edges form a tree.)

The next line contains a positive integer $Q$, representing the total number of operations performed by ufozgg.

The next $Q$ lines describe each operation in the order they are performed by ufozgg. Each line contains $4$ space-separated integers $op, s, t, k$, representing the starting point $s$, ending point $t$, and step frequency $k$ for the jump. If $op=0$, it indicates a "weakening operation"; if $op=1$, it indicates a "statistical operation."

Output

For each "statistical operation," output one integer per line, representing the sum of the toxicity values of all problems counted in that statistical operation.

Examples

Input 1

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

Output 1

10
8
6
5

Input 2

(See provided file)

Constraints

For $100\%$ of the data, it is guaranteed that $n \leq 50000$, $Q \leq 400000$, $1 \leq a_i \leq {10}^{13}$, and for all operations, $0 \leq op \leq 1$ and $1 \leq s, t, k \leq n$.