题面描述

happygod想要小林同学帮他做一个酒鬼地图。

酒鬼地图是基于酒鬼村而产生的地图，小林同学很好奇于是上社交网站找到了酒鬼村和酒鬼地图的介绍：

1. 酒鬼村里一共有 $n$ 个酒馆和 $n-1$ 条把所有酒馆连接成一个连通块的路径，形成一个树形结构，每个酒馆都有一个酒精度，其中第 $i$ 个酒馆的酒精度为 $a_i(1 \leq a_i \leq 10^9)$ 。而酒鬼地图就是从酒鬼村里面选若干个酒馆形成的地图，一个酒鬼地图的难度就是酒鬼地图上所有酒馆的酒精度之和。
2. 喝了酒鬼村的酒之后，挑战者就迷失方向了，所以不会走回头路，简而言之，酒鬼地图从第一个酒馆开始按顺序到达最后一个酒馆的过程中，不会重复走两条相同的路径。
3. 酒鬼地图必须从一号酒馆出发。

了解完这些之后，小林同学发现他什么也不会，但是他会等差数列。假如每次加入到酒鬼地图上的酒馆的编号都在某一个等差数列上，那么这个酒鬼地图将会很有意思。

为了不让happygod觉得小林同学制作的酒鬼地图太简单，小林同学要让酒鬼地图的难度系数尽量大。但是除了等差数列，小林同学就不会了，所以他来求助你。

小林同学想要做 $q(1 \leq q \leq 3 \times 10^5)$ 个酒鬼地图，每次会给你一个正整数 $d(1 \leq d < n \leq 3 \times 10^5)$ ，表示一个以 $1$ 为首项 $d$ 为公差的等差数列，每一次你只能选编号在这个等差数列上的酒馆加入到酒鬼地图中（不在酒鬼地图上的酒馆可以经过），并且这些酒馆要按照酒鬼地图的规则的情况下使得酒鬼地图难度最大。

输入

输入包含 $1+n+q$ 行，第一行包含两个正整数 $n,q$ 分别表示酒馆个数、询问个数。第二行包含 $n$ 个正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个酒馆的酒的酒精度 。接下来 $n-1$ 行，每行两个正整数 $x, y \ (x\neq y,1 \leq x,y \leq n)$ 表示第 $x$ 个酒馆和第 $y$ 个酒馆之间有一条直接连通的路径。接下来 $q$ 行，每行一个正整数 $d$ 表示每次给出的公差。

输出

对于每组数据输出 $q$ 行，每行一个正整数，表示答案。

样例输入：

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

样例输出：

 16
 34
 10
 5
 34

注：

对于前 $30\%$的数据：$1\leq n,q \leq 10^3$