字符串模板题（whiteqwq）
【题目背景】
众所周知， whiteqwq 是原题自动机， 你在 codeforces gym 上面随便找一道冷门题 打开提交记录都可以看到 whiteqwq 的提交。
【题目描述】
whiteqwq 给了你一个长度为 n 的数组 $z_1$ , $z_2$ , . . . , $z_n$ ，其中 0 $\leq$ $z_i$ < $p$ 为整数。
whiteqwq 称一个长度为 m 的数组 $x_1$ , $x_2$ , . . . , $x_m$ 是 $(a, b)$ - 回文的当且仅当 $ ∀i ∈ [1, m] 有 a * x_i + b ≡ x_{m−i+1} (mod p)$ ，或者说 $ a * x_i + b $ 除以 $p$ 的余数和 $x_{m-i+1}$ 除以 $p$ 的 余数相同。
现在 whiteqwq 有 $q$ 个询问， 令 z[l; r] 表示数组 $zl , z_{l+1}, . . . , z_r$ ，每个询问为以下两种形式中的一种：
1. 给定 $a$，询问有多少三元组 $(b, l, r)$ 满足 $z[l; r]$ 是 $(a, b)$ - 回文的， 其中要求 $1 \leq l \leq r \leq n, 0 \leq b < p$ 为整数。
2. 给定 $b$，询问有多少三元组 $(a, l, r)$ 满足 $z[l; r]$ 是 $(a, b)$ - 回文的， 其中要求 $1 \leq l \leq r \leq n, 0 \leq a < p$ 为整数。
【输入格式】
输入第一行三个正整数 n,q, p，分别表示数组长度， 询问次数以及回文串定义时需 要用的模数。
输入第二行 n 个整数 $z_1 , z_2 , . . . , z_n$ 表示 whiteqwq 给你的数组。
接下来 q 行，每行两个整数表示一次询问，每次询问有以下两种形式：
1. $1$ $a$，询问有多少三元组 $(b ,l, r)$ 满足 $z[l; r]$ 是 $(a, b)$- 回文的， 其中要求 $1 \leq l \leq r \leq n, 0 \leq b < p$ 为整数，保证 $0 \leq a < p$。
2. $2$ $b$，询问有多少三元组 $(a ,l, r)$ 满足 $z[l; r]$ 是 $(a, b)$- 回文的， 其中要求 $1 \leq l \leq r \leq n, 0 \leq a < p$ 为整数，保证 $0 \leq b < p$。
【输出格式】
输出共 $q$ 行，每行一个整数表示该次询问的答案。
【样例 1 输入】
3 3 6
1 2 1
1 0
2 0
1 1【样例 1 输出】
3
5
4【样例 1 解释】
对于第一次询问：
字符串 $z[1; 1]$ 是 $(0, 1)$− 回文的。
字符串 $z[2; 2]$ 是 $(0, 2)$− 回文的。
字符串 $z[3; 3]$ 是 $(0, 1)$− 回文的
对于第二次询问：
字符串 $z[1; 1]$ 是 $(1, 0)$− 回文的。
字符串 $z[1; 3]$ 是 $(1, 0)$− 回文的。
字符串 $z[2; 2]$ 是 $(1, 0)$− 回文的。
字符串 $z[2; 2]$ 是 $(4, 0)$− 回文的。
字符串 $z[3; 3]$ 是 $(1, 0)$− 回文的。
对于第三次询问：
字符串 $z[1; 1]$ 是 $(1, 0)$− 回文的。
字符串 $z[1; 3]$ 是 $(1, 0)$− 回文的。
字符串 $z[2; 2]$ 是 $(1, 0)$− 回文的。
字符串 $z[3; 3]$ 是 $(1, 0)$− 回文的。
【样例 2】
见选手目录下的 whiteqwq/whiteqwq2.in 与 whiteqwq/whiteqwq2.ans。 该组样例性质同测试点 1。
【样例 3】
见选手目录下的 whiteqwq/whiteqwq3.in 与 whiteqwq/whiteqwq3.ans。 该组样例性质同测试点 4。
【样例 4】
见选手目录下的 whiteqwq/whiteqwq4.in 与 whiteqwq/whiteqwq4.ans。 该组样例性质同测试点 6。
【样例 5】
见选手目录下的 whiteqwq/whiteqwq5.in 与 whiteqwq/whiteqwq5.ans。 该组样例性质同测试点 13。
【样例 6】
见选手目录下的 whiteqwq/whiteqwq6.in 与 whiteqwq/whiteqwq6.ans。 该组样例性质同测试点 22。
【测试点】
| 测试点 | $ n $ | $ q $ | $ p $ | 特殊性质 A | 特殊性质 B |
|---|---|---|---|---|---|
| $1$ | $\le 20$ | $\le 20$ | $\le 10^2 $ | 否 | 否 |
| $2,3$ | $\le 10^2$ | $\le 10^2 $ | $\le 10^9$ | 否 | 否 |
| $4,5$ | $\le 10^3$ | $\le 10^3$ | $\le 10^9$ | 是 | 否 |
| $6,7$ | $\le 10^3$ | $\le 10^3 $ | $\le 10^9$ | 否 | 是 |
| $8,9$ | $\le 10^3$ | $\le 10^3 $ | $\le 10^9$ | 否 | 否 |
| $10$~$12$ | $\le 10^3 $ | $\le 10^4$ | $\le 10^9$ | 否 | 否 |
| $13$~$15$ | $\le 2 * 10^5 $ | $\le 10^4$ | $\le 10^4$ | 否 | 否 |
| $16$~$18$ | $\le 2 * 10^5 $ | $\le 10^4$ | $\le 10^9$ | 是 | 否 |
| $19$~$21$ | $\le 2 * 10^5 $ | $\le 10^4$ | $\le 10^9$ | 否 | 是 |
| $22$~$25$ | $\le 2 * 10^5 $ | $\le 10^4$ | $\le 10^9$ | 否 | 否 |
特殊性质 A：保证询问操作只存在询问 1 a。
特殊性质 B：保证 $p$ 为质数。
对于所有数据，满足 $1 ≤ n ≤ 2 × 10^5$ , $1 ≤ q ≤ 10^4$ , $2 ≤ p ≤ 10^9$ , $0 ≤ z_i < p$。