开罗尔网络的备用连接方案
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

山姆为了让美洲各个据点接入开罗尔网络设计了一个方案，美洲各个据点的连接可视为一棵根节点为 1，大小为 n 的有根树，山姆初始位于根节点的UCA总部，而开罗尔网络的接入依据节点的不同而消耗不同类型的开罗尔晶体。具体来说，每个据点都有一个权值 a_i，而接入据点 i 需要消耗 1 个开罗尔晶体，其类型为从根节点到当前节点的简单路径上所有节点的按位与的二进制下 1 的个数，现在山姆想知道他消耗每种类型的开罗尔晶体的数目。

更形式化的说：给定一个无向边树，根为 1，节点编号为 1 ~ n 。每个节点有点权 a_i。
定义 f(u,v) 为 路径端点为 u,v 的路径上的所有点权按位与的结果。
进行 q 次询问，每次询问你需要输出 \sum^n_{i=1} [f(1,i)的二进制下1的个数是x] 。（ [] 内语句为真则值为 1，否则值为 0。）

输入描述:

第一行两个数字 n,q \ (1 \leq n \leq 10^{5},1 \leq q \leq 50) 分别代表树的大小和查询次数。
接下来一行 n 个数表示每个点的点权 a_i。( 0\leq a_i<2^{31} )
接下来 n-1 行每行两个数 u,v  (1\le u,v\le n) 分别代表一条边所连接的两个端点的编号。
在接下来 q 行每行一个数 x(1 \leq x \leq 32) 表示每个查询。

输出描述:

对于每个查询，输出一行，每行一个数 m 表示山姆所需第 x 种开罗尔晶体数量。
示例1

输入

复制 
2 1
3 7
1 2
2

输出

复制 
2

说明