UPDTARR - Arithmetic Progression Query
You have an array of size N initially filled with 0. You have Q queries. In each query, you will be given two integers a and b. For each query, you need to add 1 at the following valid indices: ... ... , a - 2*b, a - b, a, a + b, a + 2 * b ... ... The indices that lie in the range [1,n] are only considered valid. Print the final array after the last update.
The first line contains the number of test cases. Then T test cases follow. Every test case starts with two integers N and Q. After that, Q lines follow. In each line there will be two integers describing that query.
1 <= T <= 10
1 <= N, Q, a, b <= 100000
Print the final array after the last query with the case number.
1 2 Output: Case 1: 1 0 1 0 1
Nice problem. The key is in the data structure used.
Please give the range of input parameters.