E. Прибавления на отрезках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гриша пришел на контест и увидел там следующую задачу.

Дан массив длины $$$n$$$, изначально состоящий из нулей. Элементы массива пронумерованы от $$$1$$$ до $$$n$$$. К массиву было применено $$$q$$$ операций. $$$i$$$-я операция задается тремя целыми числами $$$l_i$$$, $$$r_i$$$ и $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$), ($$$1 \leq x_i \leq n$$$) и означает, что к элементам с номерами $$$l_i, l_i + 1, \ldots, r_i$$$ прибавили число $$$x_i$$$. Требуется найти максимум в массиве после применения всех этих операций.

Но Гриша не из глупых! Он решил эту задачу очень быстро.

Однако что-то в нем переклинило, и он задумался: «интересно, а какие значения может принять максимум в массиве после применения некоторого подмножества данных операций?».

Помогите Грише, найдите все такие целые числа $$$y$$$ от $$$1$$$ до $$$n$$$, что после применения некоторого (возможно, пустого) подмножества данных операций максимум в массиве равен $$$y$$$.

Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 10^{4}$$$) — длина массива и количество запросов в исходной задаче.

В следующих $$$q$$$ строках описаны запросы, по одному в строке. $$$i$$$-я из этих строк содержит три целых числа $$$l_i$$$, $$$r_i$$$ и $$$x_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1 \leq x_i \leq n$$$), что обозначает запрос на добавление числа $$$x_i$$$ на отрезке с $$$l_i$$$-го по $$$r_i$$$-й элемент включительно.

Выходные данные

В первую строку выведите единственное число $$$k$$$, обозначающее количество возможных целых чисел от $$$1$$$ до $$$n$$$, которым может быть равен максимум в массиве после применения некоторого (возможно, пустого) подмножества данных операций.

В следующей строке выведите через пробел все $$$k$$$ чисел от $$$1$$$ до $$$n$$$ — возможные значения максимума. Выводите эти числа в возрастающем порядке.

Примеры
Входные данные
4 3
1 3 1
2 4 2
3 4 4
Выходные данные
4
1 2 3 4
Входные данные
7 2
1 5 1
3 7 2
Выходные данные
3
1 2 3
Входные данные
10 3
1 1 2
1 1 3
1 1 6
Выходные данные
6
2 3 5 6 8 9
Примечание

Если в первом тестовом примере оставить только первый запрос, то максимум будет равен $$$1$$$. Если оставить только второй запрос, то максимум будет равен $$$2$$$. Если оставить первые два запроса, то максимум будет равен $$$3$$$. Если оставить только третий запрос, то максимум будет равен $$$4$$$. Но если оставить третий запрос и еще какой-то, максимум будет больше $$$n$$$, поэтому его выводить не требуется.

Во втором тестовом примере, оставив только первый запрос, можно получить $$$1$$$. Оставив только второй, можно получить $$$2$$$. А если оставить все запросы, максимум будет равен $$$3$$$.

В третьем тестовом примере можно получить максимумы так:

  • Можно получить максимум $$$2$$$ оставив запросы: $$$(1)$$$.
  • Можно получить максимум $$$3$$$ оставив запросы: $$$(2)$$$.
  • Можно получить максимум $$$5$$$ оставив запросы: $$$(1, 2)$$$.
  • Можно получить максимум $$$6$$$ оставив запросы: $$$(3)$$$.
  • Можно получить максимум $$$8$$$ оставив запросы: $$$(1, 3)$$$.
  • Можно получить максимум $$$9$$$ оставив запросы: $$$(2, 3)$$$.