C. Cursed Queries
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a cursed number $$$m$$$ and an array $$$a$$$ of length $$$n$$$.

You will then be given $$$q$$$ queries. Each query is of one of the following two types:

  1. 1 i x — Assign $$$a_i \gets x$$$.
  2. 2 l r k — Determine the $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$.

Your task is to process all the queries and print the result for each type 2 query.

A number is called good if it is not divisible by the cursed number $$$m$$$.

A number $$$x$$$ is called $$$k$$$-good if $$$x$$$ remains good after adding $$$k$$$ to it any number of times.

The $$$k$$$-goodness of an array $$$a$$$ is the number of elements in the array that are $$$k$$$-good.

A subarray of an array is a contiguous portion of it. Formally, if $$$a$$$ is an array of size $$$n$$$ and $$$1 \le l \le r \le n$$$, an array $$$a[l\,\dots\,r] = [a_l, a_{l+1}, \dots, a_r]$$$ is called a subarray of $$$a$$$.

The $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$ is the number of integers $$$i \: (l \le i \le r)$$$ such that $$$a_i$$$ is $$$k$$$-good.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 5000$$$) — the size of the array and the cursed number.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries. Each of the next $$$q$$$ lines describes a query.

Each query is of one of the following two types:

  1. 1 i x ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) — Assign $$$a_i \gets x$$$.
  2. 2 l r k ($$$1 \le l \le r \le n$$$, $$$1 \le k \le 10^9$$$) — Determine the $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$. It is also guaranteed that each test case contains at least one query of type 2.

Output

For each query of type 2, print a single line containing one integer — the $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$.

Example
Input
2
9 8
1 5 8 1 6 6 8 6 5
8
1 2 9
2 2 9 12
1 4 6
2 4 8 4
2 5 5 7
1 6 10
2 3 9 6
2 9 9 3
5 10
1 2 3 4 5
5
2 1 5 1
2 1 5 2
2 1 5 3
2 1 5 4
2 1 5 5
Output
6
4
0
1
0
0
3
0
3
4
Note

In the first test case, the cursed number is $$$8$$$.

After the first query, the array will become $$$[1, 9, 8, 1, 6, 6, 8, 6, 5]$$$.

For the second query, the $$$12$$$-goodness of the subarray $$$[9, 8, 1, 6, 6, 8, 6, 5]$$$ is $$$6$$$.

For the fourth query, the $$$4$$$-goodness of the subarray $$$[6, 6, 6, 8, 6]$$$ is $$$4$$$.