L-Misaka Mikoto's Dynamic KMP Problem_2026牛客五一集训派对day5

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

Misaka Mikoto has a pattern string $s$ . Let $|s|$ be the length of $s$ , $s_i$ be the $i$ -th character of $s$ , and $s[l\sim r]$ be the substring from the $l$ -th character to the $r$ -th character, that is, $s_ls_{l+1}\cdots s_{r}$ .
In this problem, all characters are represented by an integer.

You need to perform $m$ operations. There are two types of operations:

$1\ x\ c$ : change $s_x$ to $c$ .
$2\ t$ : given a text string $t$ , find the number of times $s$ occurs as a substring in $t$ and the longest border of $s$ .

The longest border of $s$ means the largest number $r(1\le r<|s|)$ that $s[1\sim r]$ is the same as $s[(|s|-r+1)\sim|s|]$ . If such $r$ doesn't exist, let the longest border of $s$ be $0$ .

Let's call the operation $2$ "query".

Given two integers $b,p$ , let $x_i,y_i$ be the answer to the first and the second question of the $i$ -th query, you only need to output $\left(\sum\ x_i \times y_i \times b^i\right) \bmod p$ .

For some reason, the operations are encrypted. Let $z$ be the value of $x_i \times y_i$ of the last query (if there aren't any queries before, let $z$ be $0$ ). For operation $1$ , you are given two integers $x',c'$ , which means $x=(x'\oplus z)\bmod |s|+1$ and $c=c'\oplus z$ . For operation $2$ , you are given an integer $n$ and $n$ integers $t'_1\sim t'_n$ , which means $|t|=n$ and $t_i=t'_i\oplus z$ .

输入描述:

The first line contains four integers .
The second line contains  integers, which represent the string .
The -th line of the following  lines contains the -th operation:  or .

输出描述:

One integer that represents the answer.

示例1

输入

复制

3 3 10 1000000007
1 2 1
2 5 1 2 1 2 1
1 3 3
2 4 3 3 3 3

输出

复制

备注:

For all test cases,
.
, where  represents the sum of  of all queries.
.
.