소수와 쿼리

소수 $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 - $\displaystyle\sum_{i=L}^{R}{V(A_i^S - (A_i \bmod P)^S)}$를 출력한다.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 세 개의 양의 정수 $N$, $Q$, $P$가 주어진다. $N$은 배열의 원소 수, $Q$는 쿼리의 수, $P$는 소수이다.

다음 줄에는 배열 $A$의 원소를 나타내는 $N$개의 양의 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 주어진다.

이어지는 $Q$개의 줄에는 각각 하나의 쿼리가 주어지며, 다음 중 하나의 형태이다.

• 공백으로 구분된 $3$개의 양의 정수: 1 pos val
• 또는 공백으로 구분된 $4$개의 양의 정수: 2 S L R

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 각 타입 $2$ 쿼리의 답을 나열한 목록이다.

• $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에서

첫 번째 쿼리는 $S=3$, $L=3$, $R=4$인 타입 $2$ 쿼리이다. 이 쿼리의 결과를 계산해 보자.

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

두 번째 쿼리는 타입 $1$ 쿼리로, $A_1$에 $69$를 대입해야 하므로 배열 $A$는 69 94 62 67 91이 된다.