题目描述

你有一棵以 $1$ 为根的圣诞树，上面挂着一堆礼物，共计 $m$ 种。一开始每个点上都挂着一个礼物，第 $i$ 个点的礼物类型是 $a_i$。第 $k$ 种礼物有一个价值 $v_k$。

现在你可能会进行两种操作：

1. 收到新的礼物并将其挂在树上的某个结点，并取下之前挂的礼物。
2. 观察圣诞树上所有类型为 $k$ 的礼物。对于每一棵子树，你都希望这棵子树里种类为 $k$ 的礼物的价值和为 $C$（一个常数）。然而这一般情况下不大能实现，所以你想用一个类似于方差的东西来表示你的不满意程度。定义你的不满意度为 $\displaystyle \sum^n_{i=1} (S_i-C)^2$，其中 $S_i$ 为以 $i$ 为根的子树内所有类型为 $k$ 的礼物的价值和。试着求出这个不满意度。

输入格式

第一行四个数 $n,m,q,C$，分别表示点的个数，礼物种类，操作个数，题目中的期望常数。

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

接下来一行 $m$ 个整数，表示 $v_i$。

接下来 $n-1$ 行，每行两个数 $u,v$，表示圣诞树上的一条 $(u,v)$。保证这些边构成一棵树。

接下来 $q$ 行，每行先是一个正整数 $op\in\{1,2\}$，表示操作类型。

如果 $op=1$，则该行输入为 1 p v，表示把类型为 $v$ 的礼物挂在 $p$ 点并取下之前挂的礼物。否则该行输入为 2 k，表示观察类型为 $k$ 的礼物。

输出格式

对所有观察操作，输出不满意度。因为不满意值略微超过 $64$ 位整数的范围，输出其对 $998244353$ 取模的结果即可。

样例

4 3 6 10
1 1 2 1
12 14 7
2 3
3 4
1 4
1 1 1
2 1
1 1 1
1 1 2
1 4 1
2 2

880
456

10 5 8 89
1 1 1 1 2 4 1 3 4 1
84 96 72 95 91
1 8
1 9
2 8
2 4
2 7
7 6
5 4
1 10
3 5
1 10 2
1 10 1
1 3 1
1 3 1
2 4
1 3 1
1 3 2
2 1

42065
194458

见下发文件中 sample3.in

见下发文件中 sample3.ans

数据范围

对于全部数据，$1\le n,m,q\le 10^5$，$1\le a_i,v,k\le m$，$1\le p\le n$，$1\le v_i\le 10^6$。

特殊性质 A：$1,n$ 的度数为 $1$，其余点度数为 $2$。

特殊性质 B：$1$ 的度数为 $n-1$。

请注意常数因子对程序运行效率的影响。