题目描述

Blackslex 在因人际关系紧张、政治压力大以及研究压力繁重而积累的压力中，找到了在植物和树木中安慰自己的方式。

Blackslex 拥有 $n$ 棵依次排成一排的植物，分别为第 $1,2,3,\ldots,n$ 棵。一开始，每棵植物中的水量为 $0$ 毫升。

他打算执行 $q$ 次浇水操作，具体如下：

• 对于每次操作，给出 $l, r$
• 对于每一棵第 $l \leq i \leq r$ 棵植物，向其浇灌 $f(i-l+1)$ 毫升的水

其中，$f(x)$ 表示 $x$ 与 $x$ 的最低有效位的乘积$^{\text{∗}}$。你的任务是，所有浇水操作结束后，计算每棵植物中的水量。

$^{\text{∗}}$ $x$ 的最低有效位的值指的是 $x$ 的二进制表示中最右侧为 $1$ 的那一位所表示的值。例如，$10=1010_2$ 的最低有效位的值为 $0010_2=2$。

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出 $n$ 个整数，表示每一棵第 $i$ 棵植物中的水量（$i=1,2,...,n$）。

样例

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

1 6 11 19 21 
3 12 10 37 18 43 22

样例说明

在第一个样例中，每次操作的细节如下：

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

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

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

由 ChatGPT 5 翻译

来源

Codeforces 2179H，英文题名 Blackslex and Plants。