EOJ-自适应编程学习平台

给定一棵节点数为$n$的树，每个树都有一个值$W_i$。

$q$次询问，询问对于起点$u$和终点$v$，有一个简单路径数组$P$，计算路径长度$|P|$和路径哈希$(\sum_{i=0}^{|P|-1}W_{P[i]}*B^{|P|-1-i}) \mod M$。

例如有一条路径为$1 \to 2 \to 3$，路径哈希是$(W_1 * B^2 + W_2 * B + W_3) \mod M$。

第一行四个整数$n,q,B,M$

接下来一行，$n$个整数表示$W_i$

接下来$n-1$行，每行两个整数$u,v$，表示节点$u$到节点$v$有一条边。

接下来$q$行，每行两个整数$u,v$，表示询问节点$u$到节点$v$​。

$n \le 10^5, q \le \min(\cfrac{n*(n-1)}{2},5*10^5)$

$B,M,W_i \le 10^9$

$q$行结果，路径长度和路径哈希。