P8947 Angels & Demons

The Pope’s chamberlain had already felt pain in his body. The pain quickly spread through his whole body, making him want to grab and scratch. > Do not forget the suffering Jesus endured. He felt a burning pain in his throat, and even morphine could not relieve it. > What I had to do here is already done. He had stirred awe in people’s hearts, and people had hope again. When he was in the Pallium niche, the Pope’s chamberlain followed God’s teaching and performed the anointing ritual. His body, his hair and beard, his cheeks, his linen robe—everything was covered with lamp oil. At this moment, it was as if he were soaked in sacred green lamp oil, smelling sweet like a mother’s natural scent, yet highly flammable. He would be fortunate to ascend to Heaven. It would be a miraculous and swift process. What he would leave to the world would no longer be scandal... but a new power and a miracle. His hand slipped into the pocket of his robe and took out the small golden lighter he had brought from the Pallium niche. He softly spoke a sentence that God had said at the Last Judgment. > Blazing flames rush into the sky, and God’s angels will also ascend in the fire. His thumb pressed down on the lighter. People were still singing hymns in St. Peter’s Square...

Given $n$ template strings $S_{1...n}$ consisting of lowercase letters, and $q$ queries. The queries are of the following two types: 1. `1 T`: Given a query string $T$ consisting of lowercase letters. 2. `2 p l r`: Let $num(p,l,r)$ denote how many query strings have the substring $S_p[l,r]$ as a substring. Compute $\max\limits_{i=1}^{l}(num(p,i,r))$.

The first line contains three integers $n, q, w_0$, where $w_0$ indicates the data type. * $w_0 = 0$: Lines $2$ to $n + 1$ each contain one string. Line $i + 1$ gives $S_i$. The next $q$ lines each contain one query, in the format described above. * $w_0 = 1$: The second line contains three integers $A, B, C$. The next $n$ lines each contain one string, representing a template string. Then, the queries are generated by the following code (in the code, ```lst``` denotes the answer of the previous type $2$ query, initially $0$; ```le[i]``` denotes the length of template string $i$; and ```s``` is a char array): ```cpp while (q--) { int op; scanf("%d", &op); if (op == 1) { scanf("%s", s + 1); int x((1ll * A * lst + B) % C), l(strlen(s + 1)); for (int i(1); i r) swap(l, r); // update lst here } } ```

For each type $2$ query, output one line containing one integer, the answer.

Constraints for $100\%$ of the testdata: $1 \le n, q \le 10^5$, $\sum\limits_{i=1}^{n}|S_i| \le 5 \times 10^5$, $\sum|T| \le 5 \times 10^5$, $1 \le p \le n$, $w_0 \in \{0,1\}$, $1 \le A, B < C \le 10^9$. |Test Point|Score|$n \le$|$\sum\limits_{i=1}^{n}\|S_i\|\le$|$q \leq$|$\sum \|T\| \leq$|$w_0=$|Other Limits| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$3$|$20$|$200$|$200$|$5000$|$0$|None.| |$2$|$3$|$200$|$2000$|$200$|$5000$|$0$|None.| |$3$|$3$|$200$|$2000$|$200$|$5000$|$0$|None.| |$4$|$3$|$200$|$2000$|$200$|$5\times10^5$|$0$|None.| |$5$|$3$|$200$|$2000$|$200$|$5\times10^5$|$0$|None.| |$6$|$3$|$1$|$5\times10^5$|$2$|$5\times10^5$|$0$|None.| |$7$|$3$|$1$|$5\times10^5$|$2$|$5\times10^5$|$0$|None.| |$8$|$4$|$10^5$|$10^5$|$10^5$|$10^5$|$0$|None.| |$9$|$3$|$10^5$|$10^5$|$10^5$|$10^5$|$0$|Strings are random.| |$10$|$4$|$10^5$|$2 \times 10^5$|$10^5$|$2 \times 10^5$|$0$|None.| |$11$|$3$|$10^5$|$2 \times 10^5$|$10^5$|$2 \times 10^5$|$0$|Strings are random.| |$12$|$4$|$10^5$|$3 \times 10^5$|$10^5$|$3 \times 10^5$|$0$|None.| |$13$|$3$|$10^5$|$3 \times 10^5$|$10^5$|$3 \times 10^5$|$0$|Strings are random.| |$14$|$4$|$10^5$|$4 \times 10^5$|$10^5$|$4 \times 10^5$|$0$|None.| |$15$|$3$|$10^5$|$4 \times 10^5$|$10^5$|$4 \times 10^5$|$0$|Strings are random.| |$16$|$4$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|None.| |$17$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|Strings are random.| |$18$|$3$|$10^5$|$2 \times 10^5$|$10^5$|$5\times10^5$|$0$|None.| |$19$|$3$|$10^5$|$3 \times 10^5$|$10^5$|$5\times10^5$|$0$|None.| |$20$|$3$|$10^5$|$4 \times 10^5$|$10^5$|$5\times10^5$|$0$|None.| |$21$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|Strings are random.| |$22$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|None.| |$23$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|None.| |$24$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|None.| |$25$|$3$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$0$|None.| |$26$|$4$|$10^5$|$3\times10^5$|$10^5$|$5\times10^5$|$1$|None.| |$27$|$4$|$10^5$|$4\times10^5$|$10^5$|$5\times10^5$|$1$|None.| |$28$|$4$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$1$|None.| |$29$|$4$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$1$|None.| |$30$|$4$|$10^5$|$5\times10^5$|$10^5$|$5\times10^5$|$1$|None.| Test points $8$ to $17$ guarantee that for all type $2$ queries, $l = 1$. Translated by ChatGPT 5