H. Blackslex и растения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Blackslex нашел утешение в растениях и деревьях среди накопившегося стресса от напряженных отношений, стрессовой политики и напряженных исследований.

У Blackslex есть $$$n$$$ растений, расположенных в прямой линии $$$1, 2, 3, \ldots n$$$. Изначально у каждого растения есть $$$0$$$ миллилитров воды.

Он хочет выполнить $$$q$$$ операций полива следующим образом:

  • Для каждой операции даны $$$l, r$$$
  • полить $$$f(i-l+1)$$$ миллилитров воды на $$$i$$$-е растение для каждого $$$l \leq i \leq r$$$
где $$$f(x)$$$ обозначает произведение $$$x$$$ и значение наименьшего значащего бита $$$x$$$ $$$^{\text{∗}}$$$ Ваша задача — выяснить количество воды в каждом растении после выполнения всех операций полива.

$$$^{\text{∗}}$$$Значение наименьшего значащего бита $$$x$$$ — это значение самого правого бита в двоичном представлении $$$x$$$. Например, значение наименьшего значащего бита $$$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, 3, \ldots, 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$$$ миллилитров