题目背景

不远的一年前，小 V 还是一名清华集训的选手，坐在机房里为他已如风中残烛的OI 生涯做最后的挣扎。而如今，他已成为了一名光荣的出题人。他感到非常激动，不禁感叹道： “Hello world!”。

题目描述

小 V 有 $n$ 道题，他的题都非常毒瘤，所以关爱选手的 ufozgg 打算削弱这些题。为了逃避削弱，小 V 把他的毒瘤题都藏到了一棵 $n$ 个节点的树里（节点编号从 $1$ 至 $n$），这棵树上的所有节点与小 V 的所有题一一对应。小 V 的每一道题都有一个毒瘤值，节点 $i$ （表示标号为 $i$ 的树上节点，下同）对应的题的毒瘤值为 $a_i$。

魔法师小 V 为了保护他的题目，对这棵树施了魔法，这样一来，任何人想要一探这棵树的究竟，都必须在上面做跳跃操作。每一次跳跃操作包含一个起点 $s$ 、一个终点 $t$ 和一个步频 $k$ ，这表示跳跃者会从 $s$ 出发，在树上沿着简单路径多次跳跃到达 $t$ ，每次跳跃，如果从当前点到 $t$ 的最短路长度不超过 $k$ ，那么跳跃者就会直接跳到 $t$ ，否则跳跃者就会沿着最短路跳过恰好 $k$ 条边。

既然小 V 把题藏在了树里， ufozgg 就不能直接削弱题目了。他就必须在树上跳跃，边跳跃边削弱题目。 ufozgg 每次跳跃经过一个节点（包括起点 $s$ ，当 $s = t$ 的时候也是如此），就会把该节点上的题目的毒瘤值开根并向下取整：即如果他经过了节点 $i$，他就会使 $a_i = \lfloor \sqrt{a_i} \rfloor$。这种操作我们称为削弱操作。

ufozgg 还会不时地希望知道他对题目的削弱程度。因此，他在一些跳跃操作中会放弃对题目的削弱，转而统计该次跳跃经过节点的题目毒瘤值总和。这种操作我们称为统计操作。

吃瓜群众绿绿对小 V 的毒瘤题和 ufozgg 的削弱计划常感兴趣。他现在想知道ufozgg 每次做统计操作时得到的结果。你能帮帮他吗？

输入格式

从文件 helloworld.in 中读入数据。

输入的第一行一个正整数 $n$ ，表示树的节点数。

接下来一行 $n$ 个用空格隔开的正整数 $a_1, a_2, \ldots, a_n$，依次描述每个节点上题目的毒瘤值。

接下来 $n − 1$ 行，描述这棵树。每行 $2$ 个正整数 $u, v$ ，描述一条树上的边 $(u, v)$ 。（保证 $1 \leq u, v \leq n$ ，保证这 $n − 1$ 条边构成了一棵树）

接下来一行一个正整数 $Q$ ，表示 ufozgg 的操作总数。

接下来 $Q$ 行按 ufozgg 执行操作的先后顺序依次描述每个操作，每行 $4$ 个用空格隔开的整数 $op, s, t, k$ ，表示 ufozgg 此次跳跃的起点为 $s$ ，终点为 $t$ ，步频为 $k$ 。如果 $op = 0$ ，表示这是一次削弱操作；如果 $op = 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

10
8 6 5

提示

对于 $100\%$ 的数据，$n≤50000$, $Q≤400000$, $1\leq ai\leq 10^{13}$。

对于所有的操作保证 $0\leq op\leq 1$，$1\leq s,t,k\leq n$。