操作树
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给一棵n个节点的树，每个节点上有一个操作+或者和一个数字a_i，表示或者，有q次询问，每次给出四个数x_i,y_i,c,d，表示将x_i到y_i的简单路径上的节点依次拿出来组成一个操作序列，只考虑序列中的第1,1 + d,1 + 2d,1 + 3d...个操作，询问c依次进行这些操作后的最终结果，输出答案对998244353取模后的值

输入描述:

第一行为两个数n,q
接下来n-1行，每行两个数a_i,b_i，表示这棵树的边
接下来n行，每行一个‘+’或者‘*’ 和 一个数a_i，表示第i个点上的操作
接下来q行，每行四个数x_i,y_i,c,d，含义见题目描述

输出描述:

共q行，第i行输出第i个询问的答案对998244353取模后的值
示例1

输入

复制 
5 3
1 2
2 3
2 4
1 5
+ 2
* 5
+ 3
* 2
+ 10
3 5 2 1
3 5 2 3
4 5 4 1

输出

复制 
37
15
52

说明

((2 + 3) \times 5 + 2) + 10 = 37
(2 + 3) + 10 = 15
((4 \times 2)\times 5 + 2) + 10 = 52

备注:


请注意常数因子带来的影响