#216837. [GKS 2021 #D] Primes and Queries

You are given a prime number .

Let's define as the degree of in the prime factorization of . To be clearer, if then is divisible by , but not divisible by .

Also we define .

For example, when , and , since , therefore .

You are also given an array with elements. You need to process queries of types on this array:

• type query: - assign a value to the element at , i.e.
• type query: - print .

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

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

The next line contains positive integers representing elements of array .

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

• space separated positive integers:
• or space separated positive integers:

For each test case, output one line containing Case #: , where is the test case number (starting from ) and is a list of the answers for each query of type .

样例输入 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 #

The first query is a query of type , where , , . Let's calculate the result for this query:

The second query is of type , where we need to assign to , so our array now becomes: .

Limits

is a prime number.

For at most cases:

For the remaining test cases:

There will always be at least one query of type .

Test Set

Test Set