小明在公司里面上班，除了董事长外，每个人都有自己的上级，我们设定1号员工就是董事长。

公司选人完成一个任务，需要看选择的人员协调性是多少，每个员工都有自己的适配值，只要两个人的是配置值之差为3的倍数，那么我们就认为他们相配，组队的适配值就会增加1。

公司现在想要找到一组人出去完成任务，例如我们选8 9，他们需要通过5才能进行联系，这样子就相当于选了5 8 9三人去完成任务，同样的，如果选4 9，我们就会配上2 5 进行协调，因为只有加入2和5，才能让4 9进行工作交接和传递！

为了防止所有人都要经过董事长进行协调，我们约定只能在最直接管理的部门里面进行查找。例如上图中，6 7就是在3的部门里面，我们不能说他在1的部门里面，如果查询的是5和6，我们就可以说他们是在1的部门里面。

红色数字就是它的权值，那么7和10就是部门里面最适配的一对

同样的4和1也是。

第一行是一个整数，表示公司员工数量 n。  

接下来 n - 1 行，每行两个整数 u, v，表示u是v的上级。  

接下来一行，一共n个数字，表示每个节点的适配值！

接下来一个数字p，表示p个查询

接下来p行，每行两个数字x和y，表示x和y所在线路上的适配值。

p行，每行一个匹配值，表示在x到y的最短线路上，适配值为多少！

40%数据    1 \leq n \leq 1000   ， 1 \leq q \leq 1000

30%数据    1 \leq n \leq 10000   ， 1 \leq q \leq 10000

30%数据    1 \leq n \leq 100000   ， 1 \leq q \leq 100000

每个节点的匹配值 1 \leq a_i \leq 100000

数据配图如下：

样例解释：

3 4，由于选了3 4，那么我们会选择1 2 3 4这个四个人，1 2，1 4，2 4，可以有三种选择，所以适配值是3

3 5，由于选了3 5，那么我们会选择2 3 5这三个人，3 5可以进行配对，只有一种选择，所以适配值是1