题目背景

Cdm1020 十分喜欢 August-soft 出品的游戏，在游玩 august 社历届作品的时候他突然发现了一些神奇的事实。

那就是所有的人物立绘的脸都是一样的!

不过尽管如此，作为一名资深的八月厨，他依然可以敏锐的分辨出各张立绘之间的细微差异 （并不，就是同一张脸有什么好分辨的），为了进一步研究八月社的立绘水平，Cdm1020 将八月社的所有立绘都放到了一颗树上 （什么鬼啊）

（如果你不知道什么是树的话，你可以将树理解为一个无环的无向连通图）

具体来讲树上的每个节点仅保存了一张八月社的立绘，Cdm1020 通过和他的八月厨朋友们交流发现，狂热程度不同的八月厨对于同一张立绘的喜爱程度是不一样的，具体来讲每张立绘有两个属性 $a$ 和 $b$，对于一个狂热指数为 $k$ 的八月厨来讲，他对一张属性为 $(a,b)$ 的立绘的喜爱程度为 $ka+b$。

现在 Cdm1020 想要带领他的 $m$ 个狂热指数不同的朋友参观八月社的立绘（们），他希望你对于他的每一个朋友，帮他规划出一条喜爱程度之和最大的游览路线。

当然这个问题很简单，他是不会拿来烦你的。现在他真正头疼的事情是八月社新来了一个画师夏野。他的朋友们现在闹腾着想要看八月社的新立绘 （反正还是一张脸有什么好看的），所以他规定你的路线必须从一张属于 b 叔的立绘开始，到一张属于夏野的立绘结束，你能帮帮他吗？

题目描述

请忽略上面的鬼话，就当什么也没看见

一句话题意，给定一颗 $n$ 个点的树，树上每个点不是黑色就是白色，每个点有两个属性 $a$ 和 $b$。

现在多组询问，每次询问仅给出一个参数 $k$，要求你从树上找出一条路径 $(u,v)$ 使得 $u$ 和 $v$ 的颜色不同并且

$$k\times \sum_{p \in path (u-v)}p.a+\sum_{p\in path(u-v)}p.b $$

最大，对于每个询问你仅需要输出这个最大值即可（式子里面的两个和式的意思分别是路径上的点 $a$ 属性之和和路径上点的 $b$ 属性之和）。

tips: $a,b,k$ 均可正可负，并且我们不允许你不选路径，也就是说我们求出的的最大值可以是一个负数，这会发生在所有合法路径的权值都是负数的时候。

输入格式

第一行两个正整数 $n,m$ 表示树的节点个数和询问次数。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $a$ 属性的值。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $b$ 属性的值。

接下来一行 $n$ 个整数，每个数要么为 $0$ 要么为 $1$，第 $i$ 个数为 $0$ 表示第 $i$ 个点是一个白色点，为 $1$ 表示第 $i$ 个点是一个黑色点。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示存在一条从点 $u$ 到点 $v$ 的边。

接下来 $m$ 行，每行一个整数 $k$ 表示询问的参数。

输出格式

输出 $m$ 行，对于每一个询问，输出题目中给出式子的最大值。

15 15
29 -23 -14 -50 -13 -23 5 33 50 32 27 27 -9 -42 -11
-37 39 21 50 10 -42 -2 25 1 28 40 -45 -24 -29 47
0 0 1 0 0 1 1 0 0 1 0 1 0 0 0
2 1
3 1
4 3
5 2
6 2
7 2
8 4
9 1
10 2
11 5
12 3
13 5
14 3
15 9
-8
36
44
29
-5
-4
-3
-2
-1
0
1
2
3
4
5

679
3252
3988
2608
436
355
274
199
135
126
155
232
309
386
471

提示

$2 \leq n\leq 10^5$，$1 \leq m \leq 10^5$，$-10^8 \leq k \leq 10^8$

保证不会存在所有点都是黑色或者都是白色的数据，保证对于树上的任意路径，路径上点的 $a$ 属性之和的绝对值不超过$1.5×10^9$，路径上点的 $b$ 属性之和的绝对值不超过 $1.5×10^9$。