G. Sandfall
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a zero-indexed array $$$a_0, a_1, \ldots, a_{n-1}$$$ of $$$n$$$ integers, each initially equal to $$$0$$$. You have to perform $$$q$$$ update operations on it. Each operation is described by four integers $$$l$$$, $$$r$$$, $$$x$$$, and $$$v$$$, and is performed as follows: for every $$$i$$$ with $$$l \le i \le r$$$, add $$$v$$$ to $$$a_{x \,\&\, i}$$$, where $$$\&$$$ denotes the bitwise AND operation.

Print the array $$$a$$$ after all $$$q$$$ operations are performed.

Input

The first line 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 integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the size of the array and the number of operations.

Each of the next $$$q$$$ lines contains four integers $$$l$$$, $$$r$$$, $$$x$$$, and $$$v$$$ ($$$0 \le l \le r \le n - 1;$$$ $$$0 \le x \le n - 1;$$$ $$$1 \le v \le 10^6$$$) — the parameters of one operation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print $$$n$$$ integers $$$a_0, a_1, \ldots, a_{n-1}$$$ — the final array.

Example
Input
3
4 2
1 3 2 5
0 2 3 1
2 1
0 1 1 1000000
5 3
0 4 3 10
2 3 1 6
4 4 2 8
Output
6 1 11 0
1000000 1000000
34 16 10 10 0
Note

In the first test case, the array is initially $$$[0, 0, 0, 0]$$$.

The first operation has $$$l = 1$$$, $$$r = 3$$$, $$$x = 2$$$, $$$v = 5$$$. For $$$i = 1$$$: $$$2 \,\&\, 1 = 0$$$, so $$$5$$$ is added to $$$a_0$$$. For $$$i = 2$$$: $$$2 \,\&\, 2 = 2$$$, so $$$5$$$ is added to $$$a_2$$$. For $$$i = 3$$$: $$$2 \,\&\, 3 = 2$$$, so $$$5$$$ is added to $$$a_2$$$ again. Note that $$$a_2$$$ receives $$$v = 5$$$ twice during this single operation, once for $$$i = 2$$$ and once for $$$i = 3$$$. The array becomes $$$[5, 0, 10, 0]$$$.

The second operation has $$$l = 0$$$, $$$r = 2$$$, $$$x = 3$$$, $$$v = 1$$$. Here $$$3 \,\&\, 0 = 0$$$, $$$3 \,\&\, 1 = 1$$$, and $$$3 \,\&\, 2 = 2$$$, so $$$1$$$ is added to each of $$$a_0$$$, $$$a_1$$$, and $$$a_2$$$. The final array is $$$[6, 1, 11, 0]$$$.