시간 제한메모리 제한제출정답맞은 사람정답 비율
90 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)63240.000%

## 문제

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 $\displaystyle\sum_{i=L}^{R}{V(A_i^S - (A_i \bmod P)^S)}$.

## 입력

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$, $\cdots$, $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

## 출력

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$.

## 제한

• $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 (17점)

• $1 \le S \le 4$
• $1 \le A_i \le 10^3$
• $1 \le val \le 10^3$

## Test Set 2 (22점)

• $1 \le S \le 10^9$
• $1 \le A_i \le 10^{18}$
• $1 \le val \le 10^{18}$

## 예제 입력 1

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


## 예제 출력 1

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


## 힌트

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:

$i=3$, $V(62^3 - (62 \bmod 2)^3)=3$

$i=4$, $V(67^3 - (67 \bmod 2)^3)=1$

$\displaystyle\sum_{i=3}^{4}{V(A_i^3 - (A_i \bmod P)^3)} = 3+1 = 4$

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.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.