Lyra 最近迷上了刺绣，由于对字母的执念，她只喜欢在布条上绣字符串，Lyra 认为字母的大小写是不一样的，所以每个位置她一共有 $52$ 种图案的选择。
现在 Lyra 完成了一个长度为 $n$ 的字符串并把它送给了 Evan，可是作为 OIer，Evan 只对 \sout{肥宅快乐串} 本质不同的子序列感兴趣。
于是 Evan 给了你 $m$ 个询问，每次询问一个区间，你需要告诉 Evan 这个区间里有多少个本质不同的子序列，当然这个子序列得非空。
字符串 $S_{[1,|S|]}$ 的一个子序列定义为一个序列 $S_{i_1}S_{i_2} \cdots S_{i_m}$ 其中 $1 \leq i_1 \leq i_2 \leq \cdots \leq i_m$，$m$ 为子序列的长度。
本质不同的子序列表示把子序列看成字符串并去重的结果，例如 $\texttt{lzz}$ 的本质不同的子序列有 $\texttt{l,z,lz,zz,lzz}$。
当然本质不同的子序列数目可能很多，你只需要对质数 $P$ 取模即可。
输入格式
第一行四个整数 $n, m, P, tp$，$n, m, P$ 意义如题所述，$tp = 0$ 表示询问从输入读入，而 $tp = 1$ 表示询问由伪随机生成。
第二行一个长度为 $n$ 的由大小写字母组成的字符串。
若 $tp = 0$，接下来 $m$ 行，每行两个整数 $l_i, r_i$ 表示每个询问的询问区间。
若 $tp = 1$，接下来一行五个整数 $x, y, a, b, c$，询问生成方式如下：
令 $D = 10^9 + 7, u_0 = x, v_0 = y$，
$u_i = ((a \cdot u_{i - 1} + b \cdot v_{i - 1} + c \cdot i)~XOR~ans_{i-1}) \mod D$
$v_i = ((b \cdot u_{i - 1} + c \cdot v_{i - 1} + a \cdot i)~XOR~ans_{i-1}) \mod D$
$l_i = \min((u_i \mod n) + 1, (v_i \mod n) + 1)$
$r_i = \max((u_i \mod n) + 1, (v_i \mod n) + 1)$
则 $[l_i, r_i]$ 即为第 $i$ 个询问的区间。
其中 $XOR$ 表示按位异或运算，$ans_j$ 表示第 $j$ 个询问的答案，规定 $ans_0 = 0$，注意这里的 $ans_j$ 是已经对 $P$ 取过模的结果。
输出格式
为简化输出，对 $tp = 0$ 你需要输出所有询问答案的异或和，而对于 $tp = 1$，你只需要输出 $ans_m$ 即可。
样例输入输出
样例输入1
3 3 1009 0 Lzz 1 2 2 3 1 3
样例输出1
4
样例解释1
三个询问的答案分别是 $3, 2, 5$，异或和是 $4$。
样例输入2
见 $\texttt{/embroidery/ex_embroidery2.in}$
样例输出2
见 $\texttt{/embroidery/ex_embroidery2.ans}$
数据范围及约定
对于全部数据 $1 \leq n, m \leq 10^6; 10^8 \leq P \leq 10^9+7$ 是质数$; 0 < x, y, a, b, c < 10^9+7; 1 \leq l_i \leq r_i \leq n.$
令 $S$ 为字符串中出现的不同的字符数目，各个测试点限制如下表所述：
| 测试点编号 | $n$ | $m$ | $S$ | $tp$ | 测试点编号 | $n$ | $m$ | $S$ | $tp$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | $15$ | $100$ | $26$ | $0$ | 11 | $100000$ | $1$ | $10$ | $0$ |
| 2 | $20$ | $1$ | 12 | $52$ | |||||
| 3 | $1000$ | $1000$ | $2$ | 13 | $1000000$ | $1000000$ | $20$ | $1$ | |
| 4 | $10$ | $0$ | 14 | $20$ | |||||
| 5 | $30$ | $1$ | 15 | $40$ | |||||
| 6 | $52$ | 16 | $40$ | ||||||
| 7 | $50000$ | $50000$ | $3$ | 17 | $52$ | ||||
| 8 | $10$ | $0$ | 18 | ||||||
| 9 | $100000$ | $100000$ | $3$ | 19 | |||||
| 10 | $10$ | $1$ | 20 |
时间限制：$2\texttt{s}$
空间限制：$666\texttt{MB}$
