CF2179H.Blackslex and Plants

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$

Blackslex 在紧张的人际关系、高压的政治环境以及繁重的科研工作带来的持续压力中，从植物与树木中找到了慰藉。

Blackslex 拥有 $n$ 株植物，按直线排列，编号为 $1, 2, 3, \ldots, n$。初始时，每株植物中的水量均为 $0$ 毫升。

他将执行 $q$ 次浇水操作，每次操作如下：

• 给定区间 $l, r$；
• 对每个满足 $l \leq i \leq r$ 的第 $i$ 株植物，浇灌 $f(i-l+1)$ 毫升水。

其中，$f(x)$ 表示 $x$ 与其最低位的置位比特（least significant set bit）的值之积$^{\text{∗}}$。你的任务是计算所有浇水操作完成后，每株植物中的水量。

$^{\text{∗}}$ 整数 $x$ 的最低位置位比特的值，是指其二进制表示中最右侧的值为 1 的比特位所代表的数值。例如，$10 = 1010_2$ 的最低位置位比特的值为 $0010_2 = 2$。

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$、$q$（$1 \leq n, q \leq 2\cdot 10^5$）—— 分别表示植物的数量和浇水操作的次数。

每个测试用例接下来的 $q$ 行，每行包含两个整数 $l$、$r$（$1 \leq l \leq r \leq n$）—— 表示每次浇水操作的左边界和右边界。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \cdot 10^5$。

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$

对于每个测试用例，输出 $n$ 个整数，分别表示第 $i$ 株植物中的水量，其中 $i = 1, 2, 3, \ldots, n$

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

在第一种情况下，每次操作将按如下方式执行：

1. 第一次操作将：
   • 使用 $f(1-1+1) = f(1) = 1$ 毫升水浇灌第 $1$ 株植物。
   • 使用 $f(2 - 1 + 1) = f(2) = 4$ 毫升水浇灌第 $2$ 株植物。
   • 使用 $f(3 - 1 + 1) = f(3) = 3$ 毫升水浇灌第 $3$ 株植物。
   • 使用 $f(4 - 1 + 1) = f(4) = 16$ 毫升水浇灌第 $4$ 株植物。
   • 使用 $f(5 - 1 + 1) = f(5) = 5$ 毫升水浇灌第 $5$ 株植物。
2. 第二次操作将：
   • 使用 $f(2 - 2 + 1) = f(1) = 1$ 毫升水浇灌第 $2$ 株植物。
   • 使用 $f(3 - 2 + 1) = f(2) = 4$ 毫升水浇灌第 $3$ 株植物。
3. 第三次操作将：
   • 使用 $f(2 - 2 + 1) = f(1) = 1$ 毫升水浇灌第 $2$ 株植物。
   • 使用 $f(3 - 2 + 1) = f(2) = 4$ 毫升水浇灌第 $3$ 株植物。
   • 使用 $f(4 - 2 + 1) = f(3) = 3$ 毫升水浇灌第 $4$ 株植物。
   • 使用 $f(5 - 2 + 1) = f(4) = 16$ 毫升水浇灌第 $5$ 株植物。

因此，每株植物中水的总量为：

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