决斗

Problem Description

Seto Kaiba正在研究决斗。 众所周知，游戏王中有一张名叫被封印的艾克佐迪亚的卡片，抽到它的五个部位就可以直接赢得决斗胜利。 类似的，我们给出一个新的决斗规则。对于每轮决斗，会给定一个卡池，里面共有 $n$ 张卡片，第 $i$ 张卡片的类型是 $a_i$ ，同时给出一个常数 $k$ ，表示一次使用 $k$ 张相同类型的卡片即可获得胜利。每轮决斗会分为若干次决斗，每次决斗双方会抽取卡池中的一个区间作为自己的手卡。为了增加决斗的多样性，还会对卡池进行一些修改操作，这些修改是永久性的。 现在，Seto Kaiba想要知道对于当前卡池，如果你以先手身份抽到了区间 $[l,r]$ ，你有多少种使用卡片的方式直接获得胜利。假设两种直接获得胜利的选择方式分别为 $a_{c_1},a_{c_2},...,a_{c_k}$ 与 $a_{d_1},a_{d_2},...,a_{d_k}$ ，$c,d$ 是满足单调递增的有序数列。我们认为两种方式不同当且仅当至少存在一个 $i$ 满足 $1 \leq i \leq k$ 且 $c_i \neq d_i$ 。 由于答案很大，所以每轮决斗还会给定一个常数 $mod$ ， 你只需要回答答案对 $mod$ 取模后的结果即可。

Input

第一行输入一个整数 $T$ （$1 \leq T \leq 10^5$），表示决斗轮数。 对于每轮决斗，第一行输入四个整数 $n,q,k,mod$（$1 \leq n,q \leq 10^5$ , $1 \leq k \leq 50$ , $1 \leq mod \leq 998244353$），$n,k,mod$ 含义同题意描述， $q$ 表示修改与询问的总数。 下面 $1$ 行，输入 $n$ 个整数 $a_i$ ，表示每张卡片的类型 ($1 \leq a_i \leq n$)。 接下来 $q$ 行，会先输入一个整数 $op$ ，表示这次操作的类型。 若 $op = 1$ ，会继续输入三个整数 $l,r,c$ ，表示从第 $l$ 张到第 $r$ 张卡片的类型全部修改为 $c$ 。 若 $op = 2$ ，会继续输入两个整数 $c_1,c_2$ ，表示所有类型为 $c_1$ 的卡片类型都修改为 $c_2$ 。 若 $op = 3$ ，会继续输入两个整数 $l,r$ ，表示询问抽到区间 $[l,r]$ 的获胜方案数。 对于所有数据，满足 $l \leq r$ ， $n$ 的和与 $q$ 的和均不超过 $4 \times 10^5$ ，且 $n > 1000$ 的数据不超过3组。

Output

对于每次询问，输出一行一个数，表示获胜方案数对 $mod$ 取模后的结果。

Sample Input

2
8 10 2 114514
6 6 8 5 5 1 8 4
3 3 5
3 6 6
2 3 4
2 3 2
3 1 5
2 7 6
1 3 4 7
1 5 8 4
2 5 2
3 1 7
8 9 2 1919810
2 4 8 2 6 3 3 8
3 3 8
3 4 7
2 2 7
1 1 1 5
2 7 3
3 2 5
2 3 8
1 4 8 6
3 4 6

Sample Output

1
0
2
5
2
1
0
3

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）