Problem Description

You are given a prime number $P$.

Let's define $V(x)$ as the degree of $P$ in the prime factorization of $x$. To be clearer, if $V(x) = y$ then $x$ is divisible by $P^y$, but not divisible by $P^{y+1}$.

Also we define $V(0) = 0$.

For example, when $P = 3$, and $x = 45$, since $45 = 5 \cdot 3^2$, therefore $V(45) = 2$.

You are also given an array $A$ with $N$ elements. You need to process $Q$ queries of $2$ types on this array:

• type $1$ query: $1$ $pos$ $val$ - assign a value $val$ to the element at $pos$, i.e. $A_{pos} := val$
• type $2$ query: $2$ $S$ $L$ $R$ - print $\sum_{i=L}^{R} V(A_i^S - (A_i \bmod P)^S)$.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains $3$ space separated positive integers $N$, $Q$ and $P$ - the number of elements in the array, the number of queries and a prime number.

The next line contains $N$ positive integers $A_1, A_2, \ldots, A_N$ representing elements of array $A$.

Each of the next $Q$ lines describes a query, and contains either

• $3$ space separated positive integers: $1$ $pos$ $val$
• or $4$ space separated positive integers: $2$ $S$ $L$ $R$

Output Format

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is a list of the answers for each query of type $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

Hint

In Sample Case #$1$

The first query is a query of type $2$, where $S = 3$, $L = 3$, $R = 4$. Let's calculate the result for this query:

$$\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}$$

The second query is of type $1$, where we need to assign $69$ to $A_1$, so our array $A$ now becomes: $69\ 94\ 62\ 67\ 91$.

Limits

$1 \le T \le 100$

$2 \le P \le 10^9$

$P$ is a prime number.

$1 \le pos \le N$

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

For at most $10$ cases:

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

$1 \le Q \le 10^5$

For the remaining test cases:

$1 \le N \le 10^3$

$1 \le Q \le 10^3$

There will always be at least one query of type $2$.

Test Set $1$

$1 \le S \le 4$

$1 \le A_i \le 10^3$

$1 \le val \le 10^3$

Test Set $2$

$1 \le S \le 10^9$

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

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