题目描述

你有一棵以 $1$ 为根，编号为 $1\sim n$ 的有根树，第 $i$ 号节点上有一个整数权值 $a_i$。同时每一个点都被染上了红色或蓝色。初始所有点全是红色点。你需要维护这棵树，进行 $q$ 次操作。操作分若干种，具体格式如下：

• 1 x v ：使 $x$ 节点的子树中的每个节点的权值增加 $v$ 并对 $p$ 取模。
• 2 x v：将 $a_x$ 赋值为 $v$。注意不是赋值整棵子树。
• 3 x：将 $x$ 号点染成蓝色，设 $j$ 节点为 $x$ 号节点在它的红色兄弟节点中编号（不是权值）排名的前驱，将 $x$ 节点连接父亲的边删除。然后将 $x$ 节点作为儿子节点接到 $j$ 节点上，如果 $x$ 节点没有红色兄弟节点或 $x$ 节点的红色兄弟节点的编号均比 $x$ 大则什么都不做。
• 4 x：设 $S$ 为 $x$ 的子树中的节点的权值中出现次数为奇数的数组成的集合。输出集合中的每个数的 $k$ 次方之和，对 $998244353$ 取模。即 $(\sum_{z\in S}z^k)\bmod 998244353$。

特别的，数据保证每个点只能被执行 $3$ 操作至多 $1$ 次。也就是说不会出现对一个蓝色点进行 $3$ 操作的情况。

输入格式

第一行四个整数 $n,q,p,k$。
第二行 $n$ 个整数，代表初始的 $a_1,a_2,\cdots,a_n$。
接下来 $n-1$ 行，每行两个整数 $f,t$。表示一条连接 $f \leftrightarrow t$ 的双向树边。
接下来 $q$ 行，每行两个或三个整数 $op,x(,v)$。

输出格式

对于每个询问操作，输出一行一个整数表示答案。

10 10 500 1
3 2 1 2 1 3 2 1 3 4
1 4
7 8
3 6
8 10
2 3
2 5
8 9
7 2
2 1
4 1
1 3 1
2 1 2
4 1
4 3
4 6
1 4 1
3 7
1 5 1
4 5

10
5
6
4
12

提示

样例解释

样例 #1

• 询问 4 1，子树中点的权值分别为 $3,2,1,2,1,3,2,1,3,4$，$S$ 集合为 $\{1,2,3,4\}$，故答案为 $10$。
• 修改 1 3 1，树中各点权值变为 $3,2,2,2,1,4,2,1,3,4$。
• 修改 2 1 2，树中各点权值变为 $2,2,2,2,1,4,2,1,3,4$。
• 询问 4 1，子树中点的权值分别为 $2,2,2,2,1,4,2,1,3,4$，$S$ 集合为 $\{2,3\}$，故答案为 $5$。
• 询问 4 3，子树中点的编号为 $3,6$，权值分别为 $2,4$，$S$ 集合为 $\{2,4\}$，故答案为 $6$。
• 询问 4 6，由于这是一个叶子节点，子树中点的权值为它本身的权值 $4$，$S$ 集合为 $\{4\}$，故答案为 $4$。
• 修改 1 4 1，树中各点权值变为 $2,2,2,3,1,4,2,1,3,4$。
• 修改 3 7，将 $7$ 涂成蓝色，删除树中的边 $2\leftrightarrow 7$，并将 $7$ 作为儿子节点接到 $5$ 上。
• 修改 1 5 1，树中各点权值变为 $2,2,2,3,2,4,3,2,4,5$。
• 询问 4 5，子树中各点编号为 $5,7,8,9,10$，权值分别为 $2,3,2,4,5$，$S$ 集合为 $\{3,4,5\}$，故答案为 $12$。

数据范围

本题采用捆绑测试。

对于所有数据，$1\le x\le n\le 10^5$，$1\le q \le 10^5$，$0 \le a_i, v < p \le 500$，$p\ne 0$，$0\le k \le 10^9$。