## UPDTARR - Arithmetic Progression Query

no tags

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.

### Input

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

### Output

Print the final array after the last query with the case number.

### Example

```Input:
1```
`5 1`
```1 2

Output:
Case 1: 1 0 1 0 1``` Waseem Ahmed: 2021-10-04 07:57:37 Nice problem. The key is in the data structure used. [Trichromatic] XilinX: 2021-05-07 03:59:33 Please give the range of input parameters. Reply: thanks, updated. Last edit: 2021-05-07 16:25:59