背景

O Fortuna velut luna statu variabilis……

（图片来自 Phigros 曲绘，侵删。）

加强版 T512613。

题目描述

Geopelia 需要捕捉到一种特殊的，不同于黑洞的引力波。

第 $i$ 个引力波有着一个频率 $A_i$，而多个引力波会互相影响，叠加，形成一个频率更快的引力波。

具体的，对于一个长度为 $n$ 的序列 $A$，$A$ 中所有引力波叠加起来的频率 $f(A)$ 为：$\bigcup\limits_{i=1}^n A_i$。其中 $\bigcup$ 表示按位或。

现在，Geopelia 需要知道几段以同一引力波开始的区间的频率之和。

也就是说，Geopelia 要向你询问：

的值，其中 $A[l,r]$ 为 $A_l,A_{l+1},\cdots,A_{r-1},A_r$ 组成的序列。

但不幸的是，由于幽蓝边界的引力影响，某一个区间 $[l,r]$ 中所有引力波的频率可能会异或上一个值 $x$。

Geopelia 想实时更新她的数据，你可以帮帮她吗？

她知道引力波的频率可能很高，所以你只需要告诉她答案 $\bmod \ 2^{30}$ 的值就可以了。

形式化题意

给定一个长度为 $n$ 的数组 $A$，你需要完成以下 $q$ 次操作。

1. 1 l r x 将 $A_i(l\le i\le r)$ 异或上 $x$。

2. 2 l r 求：

其中 $\bigcup$ 表示按位或。

输入格式

第一行输入四个整数 $n,m,k,q$。

第二行输入一个字符串 $S$。

接下来 $k$ 行，每行输入一个字符串和一个整数，分别代表 $T_i,v_i$。

接下来 $q$ 行，每行先输入一个整数 $opt$。

若 $opt=1$，则再输入一个字符 $x$ 表示在 $S$ 末尾添加一个字符 $x$。

若 $opt=2$，则再输入两个整数 $l,r$ 表示查询有多少个 $S$ 的子串 $S^*$ 满足 $f(S^*)\in[l,r]$。

输出格式

对于每个查询，输出一行一个整数代表所求式子的值 $\bmod \ 2^{30}$ 的结果。

3 3
1 2 3
2 1 3
1 1 2 2
2 1 3

7
9

提示

样例解释

对于第一组询问：此时 $A=\{1,2,3\}$，所以答案为 $1+1\cup 2+1\cup 2\cup 3=1+3+3=7$。

对于第二组询问：此时 $A=\{3,0,3\}$，所以答案为 $3+3\cup 0+3\cup 0\cup 3=3+3+3=9$。

数据范围

本题使用 subtask 进行捆绑测试，每个 subtask 的具体分值如下：

对于所有数据，满足 $0\le a_i,x< 2^{30}$，$1\le l\le r\le n$。

INITALIZING……
SCANING……
CONNECTING……__PhigrOS Client Login
TIME_OUT!
CONNECTING……__Unknown
SUCCESS!
————————
……九……鸟……
……鸠……！
……喂？
…听得到吗？
鸠?![SIGNAL LOST]