H. Blackslex and Plants
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Blackslex has found solace in plants and trees amidst accumulated stress from strained relationships, stressful politics, and strenuous research.

Blackslex has $$$n$$$ plants ordered in a straight line, consisting of plant $$$1, 2, 3, \ldots n$$$. Initially, every plant contains $$$0$$$ millilitres of water.

He wants to perform $$$q$$$ watering operations as follows :

  • Given $$$l, r$$$ for each operation
  • water $$$f(i-l+1)$$$ millilitres of water onto the $$$i$$$-th plant for every $$$l \leq i \leq r$$$

where $$$f(x)$$$ denotes the product of $$$x$$$ and the value of the least significant set bit of $$$x$$$ $$$^{\text{∗}}$$$ Your task is to figure out the amount of water in each plant after all watering operations are done.

$$$^{\text{∗}}$$$The value of the least significant set bit of $$$x$$$ is the value of the rightmost set bit (bit that is 1) in the binary representation of $$$x$$$. For instance, the value of the least significant set bit of $$$10 = 1010_2$$$ is $$$0010_2 = 2$$$

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 2\cdot 10^5$$$) — the number of plants and the number of watering operations, respectively.

The next $$$q$$$ lines of each test case contain two integers $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — the left bound and the right bound for each watering operation.

It is guaranteed that the sum of all values of $$$n$$$ and the sum of all values of $$$q$$$ across all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers representing the amount of water in the $$$i$$$-th plant for each $$$i = 1, 2, 3, \ldots, n$$$

Example
Input
2
5 3
1 5
2 3
2 5
7 7
1 3
1 6
3 7
4 7
7 7
1 6
5 5
Output
1 6 11 19 21 
3 12 10 37 18 43 22
Note

In the first case, each operation will be performed as follows :

  1. The first operation will :
    • water the $$$1$$$-st plant using $$$f(1-1+1) = f(1) = 1$$$ millilitres of water.
    • water the $$$2$$$-nd plant using $$$f(2 - 1 + 1) = f(2) = 4$$$ millilitres of water.
    • water the $$$3$$$-rd plant using $$$f(3 - 1 + 1) = f(3) = 3$$$ millilitres of water.
    • water the $$$4$$$-th plant using $$$f(4 - 1 + 1) = f(4) = 16$$$ millilitres of water.
    • water the $$$5$$$-th plant using $$$f(5 - 1 + 1) = f(5) = 5$$$ millilitres of water.
  2. The second operation will :
    • water the $$$2$$$-nd plant using $$$f(2 - 2 + 1) = f(1) = 1$$$ millilitres of water.
    • water the $$$3$$$-rd plant using $$$f(3 - 2 + 1) = f(2) = 4$$$ millilitres of water.
  3. The third operation will :
    • water the $$$2$$$-nd plant using $$$f(2 - 2 + 1) = f(1) = 1$$$ millilitres of water.
    • water the $$$3$$$-rd plant using $$$f(3 - 2 + 1) = f(2) = 4$$$ millilitres of water.
    • water the $$$4$$$-th plant using $$$f(4 - 2 + 1) = f(3) = 3$$$ millilitres of water.
    • water the $$$5$$$-th plant using $$$f(5 - 2 + 1) = f(4) = 16$$$ millilitres of water.

Hence, the total amount of water in each plant is :

  1. $$$1$$$ millilitres
  2. $$$4 + 1 + 1 = 6$$$ millilitres
  3. $$$3 + 4 + 4 = 11$$$ millilitres
  4. $$$16 + 3 = 19$$$ millilitres
  5. $$$5 + 16 = 21$$$ millilitres