C. Hello world!

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

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

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

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

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

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

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

接下来一行 个用空格隔开的正整数 ，依次描述每个节点上题目的毒瘤值。

接下来 行，描述这棵树。每行 个正整数 ，描述一条树上的边 。（保证 ，保证这 条边构成了一棵树）

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

接下来 行按 ufozgg 执行操作的先后顺序依次描述每个操作，每行 个用空格隔开的整数 ，表示 ufozgg 此次跳跃的起点为 ，终点为 ，步频为 。如果 ，表示这是一次削弱操作；如果 ，表示这是一次统计操作。

对于每个统计操作，输出一行一个整数，表示此次统计操作统计到的所有题的毒瘤值总和。

样例输入 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

样例输出 1

10
8
6
5

样例 2

见附加文件

对于 的数据，保证 ，，，对于所有的操作保证 ，。