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

hide comments
yoasobi: 2023-09-21 17:19:36

sqrt heuristic

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

Added by:Bertho Coder
Date:2021-05-07
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All