H. Blackslex and Plants

时间限制：每测试点 2 秒
内存限制：每测试点 512 兆字节

问题描述

Blackslex 在紧张的人际关系、压力重重的政治活动和艰辛的研究工作之余，在植物和树木中找到了慰藉。

Blackslex 有 $n$ 株植物，按直线顺序排列，分别为植物 $1, 2, 3, \dots, n$ 。最初，每株植物含有 $0$ 毫升水。

他想要执行 $q$ 次浇水操作，操作方式如下：

给定 $l, r$ 对于每次操作
对于每个 $l \le i \le r$ ，在第 $i$ 株植物上浇 $f(i-l+1)$ 毫升水，
其中 $f(x)$ 表示 $x$ 乘以 $x$ 的最低有效设置位的值 $^*$ 。

你的任务是计算所有浇水操作完成后，每株植物中的水量。

$^*$ $x$ 的最低有效设置位的值是指 $x$ 的二进制表示中最右边设置位（值为 1 的位）所对应的值。例如， $10 = 1010_2$ 的最低有效设置位的值是 $0010_2 = 2$ 。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试用例的数量。

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

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

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

输出格式

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

样例输入

样例输出

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

样例说明

在第一个测试用例中，每次操作将按如下方式进行：

第一次操作： - 给第 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 株植物浇 $f(2-2+1) = f(1) = 1$ 毫升水。 - 给第 3 株植物浇 $f(3-2+1) = f(2) = 4$ 毫升水。

第三次操作： - 给第 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$ 毫升