9091: Misaka Mikoto's Dynamic KMP Problem

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

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

• $1xc$: change sxs_xsx to $c$.
• $2t$: 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≤r<∣s∣)r(1\le r<|s|)r(1≤r<∣s∣) that s[1∼r]s[1\sim r]s[1∼r] is the same as s[(∣s∣−r+1)∼∣s∣]s[(|s|-r+1)\sim|s|]s[(∣s∣−r+1)∼∣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 xi,yix_i,y_ixi,yi be the answer to the first and the second question of the $i$-th query, you only need to output (∑ xi×yi×bi)modp\left(\sum\ x_i \times y_i \times b^i\right) \bmod p(∑ xi×yi×bi)modp.

For some reason, the operations are encrypted. Let $z$ be the value of xi×yix_i \times y_ixi×yi 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′x',c'x′,c′, which means x=(x′⊕z)mod∣s∣+1x=(x'\oplus z)\bmod |s|+1x=(x′⊕z)mod∣s∣+1 and c=c′⊕zc=c'\oplus zc=c′⊕z. For operation $2$, you are given an integer $n$ and $n$ integers t1′∼tn′t'_1\sim t'_nt1′∼tn′, which means $|t|=n$ and ti=ti′⊕zt_i=t'_i\oplus zti=ti′⊕z.

The first line contains four integers $|s|,m,b,p$.
The second line contains $|s|$ integers, which represent the string $s$.

The $i$-th line of the following $m$ lines contains the $i$-th operation: 1 x′ c′1\ x'\ c'1 x′ c′ or 2 n t1′ t2′ ⋯ tn′2\ n\ t'_1\ t'_2\ \cdots\ t'_n2 n t1′ t2′ ⋯ tn′.