Description

有一棵具有 $N$ 个节点的树（根节点为 1），他给树上每一个节点 $i$ 都评定了一个愉悦值 $C_i$。

但这棵树实在是太大了，以至于他想给它来一次剪枝：选择树上某个非叶子节点$u$，将其子树中所有与它深度差大等于 $d$ 节点全部剪掉。

现在他已经在脑海中设想了 $T$ 种可能的剪枝方式，他想请你帮他算算，对于每种给出的方式，他剪掉的那些节点的愉悦值中，最大会是多少？

Format

Input

第一行一个正整数 $N$ ，含义见上文

第二行$N$个正整数 $C_i$ ，含义见上文

接下来 $N-1$ 行，每行两个正整数 $a,b$，表示节点$a,b$有一条边

接下来一个正整数$T$,含义见上文

接下来$T$行，每行两个正整数$u,d$，含义见上文（保证输入数据合法）

Output

共$T$行输出，每行一个正整数表示对应询问的答案，含义见上文

Samples

1
10
2 1 4 7 4 8 3 6 4 7
1 2
1 3
2 4
2 5
3 6
2 7
1 8
2 9
1 10
4
1 1
1 2
2 1
3 1

8
8
7
8

Limitation