소수와 쿼리

소수 $\mathbf{P}$가 주어진다.

$x$의 소인수분해에서 $\mathbf{P}$의 지수를 $V(x)$로 정의하자. 더 명확히 말하면, $V(x) = y$이면 $x$는 $\mathbf{P}^y$로 나누어떨어지지만 $\mathbf{P}^{y+1}$로는 나누어떨어지지 않는다. 또한 $V(0) = 0$로 정의한다.

예를 들어, $\mathbf{P}=3$이고 $x=45$일 때, $45=5\cdot3^2$이므로 $V(45)=2$이다.

$\mathbf{N}$개의 원소를 가진 배열 $\mathbf{A}$도 주어진다. 이 배열에 대한 $2$가지 유형의 쿼리 $\mathbf{Q}$개를 처리해야 한다:

• 유형 $1$ 쿼리: 1 $\mathbf{pos}$ $\mathbf{val}$ - $\mathbf{pos}$에 있는 원소에 값 $\mathbf{val}$를 대입한다. 즉, $\mathbf{A_{pos}}:= \mathbf{val}$

• 유형 $2$ 쿼리: 2 $\mathbf{S}$ $\mathbf{L}$ $\mathbf{R}$ - $\sum\limits_{i=\mathbf{L}}^{\mathbf{R}} V(\mathbf{A_i}^{\mathbf{S}} - (\mathbf{A_i} \bmod \mathbf{P})^{\mathbf{S}})$를 출력한다.

제한

시간 제한: 90초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$ $2 \le \mathbf{P} \le 10^9$ $\mathbf{P}$은 소수이다. $1 \le \mathbf{pos} \le \mathbf{N}$ $1 \le\mathbf{L} \le \mathbf{R} \le \mathbf{N}$

최대 10개의 케이스에 대해: $1 \le \mathbf{N} \le 5 \times 10^5$ $1 \le \mathbf{Q} \le 10^5$

나머지 테스트 케이스에 대해: $1 \le \mathbf{N} \le 10^3$ $1 \le \mathbf{Q} \le 10^3$

유형 $\mathbf{2}$의 쿼리가 항상 적어도 하나 존재한다.

테스트 세트 1

$1 \le \mathbf{S} \le 4$ $1 \le \mathbf{A_i} \le 10^3$ $1 \le \mathbf{val} \le 10^3$

테스트 세트 2

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

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 양의 정수 $3$개, $\mathbf{N}$, $\mathbf{Q}$, $\mathbf{P}$가 주어지며, 각각 배열의 원소 수, 쿼리 수, 소수를 나타낸다. 다음 줄에는 배열 $\mathbf{A}$의 원소를 나타내는 양의 정수 $\mathbf{N}$개 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$가 주어진다. 이어지는 $\mathbf{Q}$개의 각 줄에는 쿼리 하나가 기술되며, 다음 중 하나를 포함한다.

• 공백으로 구분된 양의 정수 $3$개: 1 $\mathbf{pos}$ $\mathbf{val}$

• 또는 공백으로 구분된 양의 정수 $4$개: 2 $\mathbf{S}$ $\mathbf{L}$ $\mathbf{R}$

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이고(1부터 시작), $y$는 유형 $\mathbf{2}$의 각 쿼리에 대한 답의 목록이다.

샘플 케이스 #1에서

첫 번째 쿼리는 유형 $2$의 쿼리이며, 여기서 $\mathbf{S}=3, \mathbf{L}=3, \mathbf{R}=4$이다. 이 쿼리의 결과를 계산해 보자: $i=3, V(62^3 - (62 \bmod 2)^3) = 3$ $i=4, V(67^3 - (67 \bmod 2)^3) = 1$ $\sum\limits_{i=3}^{4} V(\mathbf{A_i}^{3} - (\mathbf{A_i} \bmod \mathbf{P})^{3})=3+1=4$ 두 번째 쿼리는 유형 $1$이며, $\mathbf{A_1}$에 $69$를 대입해야 하므로 배열 $\mathbf{A}$는 이제 다음과 같이 된다: $69 \enspace 94 \enspace 62 \enspace 67 \enspace 91$.