Seto Kaiba正在研究决斗。
众所周知，游戏王中有一张名叫被封印的艾克佐迪亚的卡片，抽到它的五个部位就可以直接赢得决斗胜利。
类似的，我们给出一个新的决斗规则。对于每轮决斗，会给定一个卡池，里面共有 nn 张卡片，第 ii 张卡片的类型是 aiai ，同时给出一个常数 kk ，表示一次使用 kk 张相同类型的卡片即可获得胜利。每轮决斗会分为若干次决斗，每次决斗双方会抽取卡池中的一个区间作为自己的手卡。为了增加决斗的多样性，还会对卡池进行一些修改操作，这些修改是永久性的。
现在，Seto Kaiba想要知道对于当前卡池，如果你以先手身份抽到了区间 [l,r][l,r] ，你有多少种使用卡片的方式直接获得胜利。假设两种直接获得胜利的选择方式分别为 ac1,ac2,...,ackac1,ac2,...,ack 与 ad1,ad2,...,adkad1,ad2,...,adk ，c,dc,d 是满足单调递增的有序数列。我们认为两种方式不同当且仅当至少存在一个 ii 满足 1≤i≤k1≤i≤k 且 ci≠dici=di 。 由于答案很大，所以每轮决斗还会给定一个常数 modmod ， 你只需要回答答案对 modmod 取模后的结果即可。
第一行输入一个整数 TT （1≤T≤1051≤T≤105），表示决斗轮数。
对于每轮决斗，第一行输入四个整数 n,q,k,modn,q,k,mod（1≤n,q≤1051≤n,q≤105 , 1≤k≤501≤k≤50 , 1≤mod≤9982443531≤mod≤998244353），n,k,modn,k,mod 含义同题意描述， qq 表示修改与询问的总数。
下面 11 行，输入 nn 个整数 aiai ，表示每张卡片的类型 (1≤ai≤n1≤ai≤n)。
接下来 qq 行，会先输入一个整数 opop ，表示这次操作的类型。
若 op=1op=1 ，会继续输入三个整数 l,r,cl,r,c ，表示从第 ll 张到第 rr 张卡片的类型全部修改为 cc 。
若 op=2op=2 ，会继续输入两个整数 c1,c2c1,c2 ，表示所有类型为 c1c1 的卡片类型都修改为 c2c2 。
若 op=3op=3 ，会继续输入两个整数 l,rl,r ，表示询问抽到区间 [l,r][l,r] 的获胜方案数。
对于所有数据，满足 l≤rl≤r ， nn 的和与 qq 的和均不超过 4×1054×105 ，且 n>1000n>1000 的数据不超过3组。
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 61
0
2
5
2
1
0
3