题目描述

给定一个素数 $P$。

定义 $V(x)$ 为 $x$ 的质因数分解中 $P$ 的次数。更明确地说，若 $V(x) = y$，则 $x$ 能被 $P^y$ 整除，但不能被 $P^{y+1}$ 整除。

此外，定义 $V(0) = 0$。

例如，当 $P = 3$ 且 $x = 45$ 时，由于 $45 = 5 \cdot 3^2$，因此 $V(45) = 2$。

你还得到一个包含 $N$ 个元素的数组 $A$。你需要处理 $Q$ 个查询，查询有两种类型：

• 类型 $1$ 查询：1 pos val – 将位置 $pos$ 上的元素赋值为 $val$，即 $A_{pos} := val$。
• 类型 $2$ 查询：2 S L R – 输出 $\sum_{i=L}^{R} V(A_i^S - (A_i \bmod P)^S)$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个空格分隔的正整数 $N$、$Q$ 和 $P$，分别表示数组的元素个数、查询的数量以及一个素数。

下一行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$，表示数组 $A$ 的元素。

接下来的 $Q$ 行每行描述一个查询，每行要么包含三个空格分隔的正整数：1 pos val，要么包含四个空格分隔的正整数：2 S L R。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是按顺序排列的每个类型 $2$ 查询的答案列表。

2
5 5 2
16 94 62 67 91
2 3 3 4
1 1 69
2 3 1 4
2 1 1 1
2 3 2 2
5 5 5
1 2 3 4 5
2 1 1 5
1 3 98
2 3 2 4
1 5 3
2 2 1 5

Case #1: 4 9 2 3
Case #2: 1 1 1

提示

在样例 #1 中：

第一个查询是类型 $2$ 查询，其中 $S = 3$，$L = 3$，$R = 4$。让我们计算该查询的结果：

$$\begin{aligned} i &= 3,\ V(62^3 - (62 \bmod 2)^3) = 3 \\ i &= 4,\ V(67^3 - (67 \bmod 2)^3) = 1 \\ &\sum_{i=3}^{4} V(A_i^3 - (A_i \bmod P)^3) = 3 + 1 = 4 \end{aligned}$$

第二个查询是类型 $1$ 查询，我们需要将 $69$ 赋给 $A_1$，因此数组 $A$ 变为：$69\ 94\ 62\ 67\ 91$。

限制条件

$1 \le T \le 100$

$2 \le P \le 10^9$

$P$ 是素数。

$1 \le pos \le N$

$1 \le L \le R \le N$

最多 $10$ 个测试用例满足：

$1 \le N \le 5 \times 10^5$

$1 \le Q \le 10^5$

其余测试用例满足：

$1 \le N \le 10^3$

$1 \le Q \le 10^3$

保证至少存在一个类型 $2$ 查询。

测试集 1

$1 \le S \le 4$

$1 \le A_i \le 10^3$

$1 \le val \le 10^3$

测试集 2

$1 \le S \le 10^9$

$1 \le A_i \le 10^{18}$

$1 \le val \le 10^{18}$

翻译由 DeepSeek V4 Pro 完成